Skip to content

Instantly share code, notes, and snippets.

@edw
Last active May 12, 2020 14:58
Show Gist options
  • Save edw/c465ea41c01a27487b3ae5748325e426 to your computer and use it in GitHub Desktop.
Save edw/c465ea41c01a27487b3ae5748325e426 to your computer and use it in GitHub Desktop.
Binary search in Python
def containsMatch(nums, lower, upper, match):
"""Returns `True` if `match` occurs within indices
[`lower`, `upper`] of sorted list `nums`."""
while True:
i = (upper + lower) // 2
cur = nums[i]
if match == cur:
return True
elif lower >= upper:
return False
elif nums[i] < match:
lower = i+1
else:
upper = i
# atLeastIndex and noMoreThanIndex are not guaranteed to find the
# highest index of a value if values are repeated.
def atLeastIndex(nums, lower, upper, atLeast):
origLower = lower
origUpper = upper
while True:
i = (upper + lower) // 2
cur = nums[i]
if cur == atLeast:
return i
elif lower >= upper:
if cur < atLeast and i < origUpper:
return i+1
elif cur < atLeast:
return None
else:
return i
elif cur < atLeast:
lower = i+1
else:
upper = i
def noMoreThanIndex(nums, lower, upper, noMoreThan):
origLower = lower
origUpper = upper
while True:
i = (upper + lower) // 2
cur = nums[i]
if noMoreThan == cur:
return i
elif lower >= upper:
if cur > noMoreThan and i > origLower:
return i-1
elif cur > noMoreThan:
return None
else:
return i
elif cur < noMoreThan:
lower = i+1
else:
upper = i
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment