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.

Advanced Usages

  • 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.

Sample Questions