이진 범위 탐색 알고리즘

binsearch.py

def withinRangeSearch(aList, key, kpick=lambda x:x[0], vpick=lambda x:x[1]):
  left = 0
  right = len(aList) - 1

  if key < kpick(aList[left]):
    return vpick(aList[left]) or left

  if key >= kpick(aList[right]):
    return vpick(aList[right]) or right

  while True:
    if left > right: # Never happen
      return None

    mid = left + (right - left) // 2

    lower = kpick(aList[mid - 1])
    upper = kpick(aList[mid])

    if key >= lower and key < upper:
      return vpick(aList[mid]) or mid

    if key >= upper:
      left = mid + 1
      continue

    if key < lower:
      right = mid - 1
      continue