Template for binary search prefer lower a lower bound. Copy-paste and edit solving more complex problems.
def search(arr, v):
low, high = 0, len(arr)
while low < high:
mid = (low + high) // 2
if arr[mid] == v:
return mid
if v < arr[mid]:
high = mid
else:
low = mid + 1
return -1
The choice of low/high/mid should ALWAYS shrink the bound
Keep in mind what happens when there are “few” elements; 0, 1, 2 may cause problems
This becomes plain old binary search if FOUND=True and NOT_FOUND=False.
The initial range should include the entire bound of things you want to find For example, we can:
Index where we want to insert v into arr (which may be at the edges)
Iterators and size types outside their natural range.
high + low overflow
Index -1.