[Python知识库]python二分查找模板

经常会遇到需要进行二分查找的情境，python中的bisect很好用，当无法使用这个库的时候，可以自己手动实现。
下面的代码片段实现了“查找target第一次出现的位置”，以及“第一个大于target的值的位置”两个功能，如果要找target最后一次出现的位置，可以在“第一个大于target的值的位置”的基础上减一。
如果第一次查找11，left和right都等于7(即数组的长度，因为11不存在于数组arr中)，需要手动判断。
下面的代码适用于剑指offer《在排序数组中查找数字》

import bisect

arr = [5, 7, 7, 8, 8, 9, 10]

# i,j辅助使用
i, j = 0, len(arr)

# left、right是需要搜索的
# left表示第一个等于target的值的位置
# right表示第一个大于target的值的位置
left = 0
right = len(arr)

# 目标值，假设需要找到数组中第一个等于8的值，以及第一个大于8的值
target = 8

# i永远等于mid加1
# j永远等于mid
# 当搜索left时，第一个条件为arr[mid]<target:i=mid+1
# 当搜索left时，第一个条件为target<arr[mid]:j=mid
while i < j:
    mid = (i + j) // 2
    if arr[mid] < target:
        i = mid + 1
        left = i
    else:
        j = mid

i = 0
j = len(arr)
while i < j:
    mid = (i + j) // 2
    if target < arr[mid]:
        j = mid
        right = j
    else:
        i = mid + 1

# 可以看到结果相同，第一次出现8的位置是3
print(bisect.bisect_left(arr,8))
print(left)

# 可以看到，第一次大于8的位置是5
print(bisect.bisect_left(arr,9))
print(right)