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.

Advanced Usages

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.

Sample Questions