Summary table

algorithm bisect_left bisect_right
lo 0 0
hi len(arr) len(arr)
criterion_1 arr[mid] >= t arr[mid] > t
bisection arr[mid:] >= t arr[mid:] > t
FFFFTTTT arr[mid] -> arr[mid] is first T
TTTTFFFF   not arr[mid] -> arr[mid-1] is last T

Remarks

• The binary search algorithm solves the problem of finding a target within a sorted sequence.
• The algorithm works by iteratively updating the lower or upper bound of the search space where the target if exist should reside.
• The update is done by checking the middle element of search space. Comparing it with the target and figure out which half of the search space it should it be.
• The algorithm runs in O(logN) time worst case, because we are iteratively cutting the search space in half.

Examples Code

• Prefer left inclusive right exclusive pattern.
1. To find a value in array:
def binary_search(arr, t):
lo, hi = 0, len(arr)
while lo < hi:           # note the equal here
mid = (hi + lo) // 2  # use l + (h - l) // 2 for non python
if arr[mid] == t:
return mid
if arr[mid] > t:
hi = mid         # new search space [lo, mid)
else:
lo = mid + 1     # new search space [mid + 1, hi)
return -1


In case the target value occurs more than once, this binary search code will find one, but not guarantee to be either leftmost or rightmost.

2. bisect left
def binary_search_left(arr, t):
lo, hi = 0, len(arr)
while lo < hi:
mid = (hi + lo) // 2
if arr[mid] >= t:
hi = mid              # new search space [lo, mid)
else:
lo = mid + 1          # new search space [mid + 1, hi)
return lo


returns i, such that arr[:i] < t and arr[i:] >= t.

Watch out the condition, if arr[mid] == t we still set hi = mid, which means, mid will be excluded from our search space, but our loop will only terminate if lo == hi, meaning we are not totally excluding this mid from be finally returned. When we search the [lo, mid) space without success, we eventually will return this mid value.

1. bisect right
def binary_search_right(arr, t):
lo, hi = 0, len(arr)
while lo < hi:
mid = (hi + lo) // 2
if arr[mid] > t:
hi = mid             # new search space [lo, mid)
else:
lo = mid + 1         # new search space [mid + 1, hi)
return lo


returns i, such that arr[:i] <= t and arr[i:] > t. if replace t < arr[mid] with f(mid): -> Bool*

2. apply to range(boolean) of function over search space python def binary_search_left(arr, func): lo, hi = 0, len(arr) while lo < hi: mid = (hi + lo) // 2 if func(arr[mid]): hi = mid # new search space [lo, mid)
else: lo = mid + 1 # new search space [mid + 1, hi) return lo

arr = list(range(20)) func = lambda x: x >= 10 idx = binary_search_left(arr, func) print(arr[idx]) # 10

returns i, such that arr[:i] == False and arr[i:] == True.

python
def binary_search_right(arr, func):
lo, hi = 0, len(arr)
while lo < hi:
mid = (hi + lo) // 2
if not func(arr[mid]):
hi = mid            # new search space [lo, mid)
else:
lo = mid + 1        # new search space [mid + 1, hi)
return lo

func = lambda x: x <= 10
idx = binary_search_right(arr, func)
print(arr[idx-1])  # 10


returns i, such that arr[:i] == True and arr[i:] == False. As a result, arr[i-1] if exist will be the last True value.