## Summary table

algorithm bisect_left bisect_right
lo 0 0
hi len(arr) len(arr)
criterion 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.
• Prefer left inclusive right exclusive pattern for bisect_left and right. But ok with exact find with both end inclusive.

• We can apply binary search on the domain of a monotonic function.
• The given sequence as a whole may not be ordered, but if we know certain subsequence is ordered, we can apply binary search on the subsequence.
• [In longest increasing / non-decreasing sub-sequence problem, binary search can be used with a stack to speed up the DP tabulation.][1]

## Examples Code

1. To find a value in array:
# both inclusive version
def binary_search(arr, t):
lo, hi = 0, len(arr) - 1               # search space [0, n - 1]
while lo <= hi:                        # both inclusive thus need = sign here
mid = (hi + lo) >> 1
if arr[mid] == t: return mid
if arr[mid] > t:  hi = mid - 1     # new search space [lo, mid - 1]
else:             lo = mid + 1     # new search space [mid + 1, hi]
return -1

# left inclusive, right exclusive
def binary_search(arr, t):
lo, hi = 0, len(arr)                   # search space [0, n)
while lo < hi:                         # right is exclusive thus no need for = sign here
mid = (hi + lo) >> 1
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.

1. 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, also the first i such that the criterion is True.

Example bisect left and bisect right on an arrary, and what happens when it go out of range.

arr = [1,2,3,3,5]
for t in range(7): print(binary_search_left(arr, t), binary_search_right(arr, t))
0 0
0 1
1 2
2 4
4 4
4 5
5 5

if replace t < arr[mid] with f(mid): -> Bool

1. apply to range(boolean) of function over search space
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 # lo = hi = the first index such that func return True

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.

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 # lo = hi = first index such that func return False

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.