Binary search

二分法。

一般 pattern

low = 0
high = n
while low <= high:
    mid = (low + high) // 2
    mid_calc = f(mid)
    if mid_calc == target:
        return g(mid)
    elif mid_calc < target:
        low = mid + 1
    else:
        high = mid - 1
return default_retval

注意 low <= high, low = mid + 1 和 high = mid - 1。while 循环结束后 low 的值是新元素的插入位置。

变化

mid 赋值为 floor((left + right) / 2) 时，需要用 left = mid + 1 和 right = mid，循环判断为 left < right

找第一次出现的下标（bisect_left）

如需找到元素第一次出现的下标（Leetcode 34. Find First and Last Position of Element in Sorted Array），可将 mid_calc 等于和大于的情况合并，并给新的 high 赋值时不 - 1。

Python 示例：

def bisect_left(arr, x):
    lo = 0
    hi = len(arr)
    while lo < hi:
        mid = (lo + hi) // 2
        if arr[mid] < x:
            lo = mid + 1
        else:
            hi = mid
    return lo

找最后一次出现的下标+1（bisect_right）

Python 示例

def bisect_right(arr, x):
    lo = 0
    hi = len(arr)
    while lo < hi:
        mid = (lo + hi) // 2
        if arr[mid] > x:
            hi = mid
        else:
            lo = mid + 1
    return lo