首先禀崖，我們完成了二分查找及其變形的 3 個(gè)函數(shù)的模板：
1、binsearch(nums, target)：標(biāo)準(zhǔn)的二分查找螟炫，找不到返回-1波附；
2、lowerbound(nums, target)：查找第一個(gè)>=target的元素索引昼钻，找不到返回?cái)?shù)組長度掸屡；
3、upperbound(nums, target)：查找第一個(gè)>target的元素索引然评，找不到返回?cái)?shù)組長度仅财。
class BinarySearch:
# 標(biāo)準(zhǔn)的二分查找，找不到返回-1
def binsearch(nums, target):
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = lo + (hi - lo) // 2
if nums[mid] == target:
return mid
elif nums[mid] > target:
hi = mid - 1
else: # nums[mid] < target:
lo = mid + 1
return -1
# 查找第一個(gè)>=target的元素索引碗淌，找不到返回?cái)?shù)組長度
def lowerbound(nums, target):
lo, hi = 0, len(nums) - 1
pos = len(nums) # 找不到
while lo < hi:
mid = lo + (hi - lo) // 2
if nums[mid] >= target:
hi = mid
else: # nums[mid] < target:
lo = mid + 1
if nums[lo] >= target: # lo就是要找的元素索引
pos = lo
return pos
# 查找第一個(gè)>target的元素索引盏求，找不到返回?cái)?shù)組長度
def upperbound(nums, target):
lo, hi = 0, len(nums) - 1
pos = len(nums) # 找不到
while lo < hi:
mid = lo + (hi - lo) // 2
if nums[mid] > target:
hi = mid
else: # nums[mid] <= target:
lo = mid + 1
if nums[lo] > target: # lo就是要找的元素索引
pos = lo
return pos
然后抖锥，我們介紹 Python 的 bisect 模塊（import bisect）：
先說明的是，使用這個(gè)模塊的函數(shù)前先確保操作的列表是已排序的碎罚。
- 有 3 個(gè)函數(shù)：
bisect.bisect(list, val)磅废、bisect.bisect_left(list, val)、bisect.bisect_right(list, val)荆烈，功能是在有序數(shù)組 list 中返回 val 插入位置的索引（不改變 list 本身）拯勉，后兩者適合包含重復(fù)元素的情況。實(shí)際上耙考，bisect.bisect(list, val)等價(jià)于bisect.bisect_right(list, val)谜喊。
import bisect
a = [1,1,2,2,2,2,3,4,4,5,5,6,6,6]
print(bisect.bisect(a, 0)) # 1
print(bisect.bisect_left(a, 6)) # 11
print(bisect.bisect_right(a, 2)) # 6
- 有 3 個(gè)函數(shù)：
bisect.insort(list, val)、bisect.insort_left(list, val)倦始、bisect.insort_right(list, val)斗遏，功能是在有序數(shù)組 list 中插入 val （會改變 list 本身）。單純看其結(jié)果的話鞋邑，3 個(gè)函數(shù)的操作結(jié)果是一樣的诵次，其實(shí)插入的位置不同而已。
import bisect
a = [1,1,2,2,2,2,3,4,4,5,5,6,6,6]
bisect.bisect(a, 0) # a = [0,1,1,2,2,2,2,3,4,4,5,5,6,6,6]
bisect.bisect_left(a, 6) # a = [0,1,1,2,2,2,2,3,4,4,5,5,6,6,6,6]
bisect.bisect_right(a, 2) # a = [0,1,1,2,2,2,2,2,3,4,4,5,5,6,6,6,6]
二分查找的變形與 bisect 模塊的關(guān)系：
1枚碗、二分查找中的 lowerbound(nums, target) 函數(shù)等價(jià)于 bisect.bisect_left(list, val)逾一；
2、二分查找中的 upperbound(nums, target) 函數(shù)等價(jià)于 bisect.bisect_right(list, val) 或 bisect.bisect(list, val)肮雨。
