二分法。
一般 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 1
找第一次出现的下标（bisect_left）
如需找到元素第一次出现的下标（Leetcode 34. Find First and Last Position of Element in Sorted Array），可将 mid_calc 等于和大于的情况合并，并给新的 high 赋值时不 - 1。
Python 示例：2
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