A simple Binary Search Template

def lower_bound(array, first, last, value)   # return first !< val in [first, last)
    while first < last: # not empty
        mid = first + (last - first)/2. # no overflow
        if array[mid] < val : first = mid + 1
        else: last = mid
    return first. # or last
  • No need to worry about onverflow:
    mid = (2 * first + last - first) / 2
  • +/- 1 only occurres one time
  • Both first and last could be returned

Here is a clear explanation in Chinese: link

Leave a Reply