python 中实现二分查找 — bisect 在python中可以使用bisect模块对一个有序的数组做二分查找，非常方便。 ## 系统用例 ```python s = [1, 2, 5, 6, 7, 9, 11] # 确保s已经排序 print(bisect.bisect(s, 2)) # 2 bisect默认从右搜索，返回的插入点index在右 print(bisect.bisect(s, 6)) # 4 print(bisect.bisect(s, 11)) # 7 print(bisect.bisect(s, 111)) # 7 print(bisect.bisect_left(s, 2)) # 1 返回的插入点index在左 print(bisect.bisect_left(s, 6)) # 3 print(bisect.bisect_left(s, 11)) # 6 print(bisect.bisect_left(s, 111)) # 7 ``` ## 新增一个search函数 bisect只能找到某个数的插入位置，这里实现一个search函数，查找是否在数组中存在某个数。 ``` # 自定义一个bisect_search函数，当查找不到，返回-1，否则返回这个数的index def bisect_search(a, x, lo=0, hi=None): index = bisect.bisect_right(a, x, lo, hi) if index == 0: return -1 else: searched = a[index-1] if searched == x: return index-1 else: return -1 print(search(s, 2)) # 1 print(search(s, 6)) # 3 print(search(s, 11)) # 6 print(search(s, 111)) # -1 ``` ## 自定义改造 默认情况下，只能对简单的数组进行二分查询， 对系统的bisect做了稍微的改造，使它支持定义一个key适配复杂的List ``` """Bisection algorithms.""" def insort(a, x, lo=0, hi=None, key=None): """Insert item x in list a, and keep it sorted assuming a is sorted. If x is already in a, insert it to the right of the rightmost x. Optional args lo (default 0) and hi (default len(a)) bound the slice of a to be searched. key (default None) defines an operation on the item before comparison. """ if not key: def key(x): return x if lo < 0: raise ValueError('lo must be non-negative') if hi is None: hi = len(a) while lo < hi: mid = (lo+hi)//2 if key(x) < key(a[mid]): hi = mid else: lo = mid+1 a.insert(lo, x) def bisect_right(a, x, lo=0, hi=None, key=None): """Return the index where to insert item x in list a, assuming a is sorted. The return value i is such that all e in a[:i] have e <= x, and all e in a[i:] have e > x. So if x already appears in the list, a.insert(x) will insert just after the rightmost x already there. Optional args lo (default 0) and hi (default len(a)) bound the slice of a to be searched. key (default None) defines an operation on the item before comparison. """ if not key: def key(x): return x if lo < 0: raise ValueError('lo must be non-negative') if hi is None: hi = len(a) while lo < hi: mid = (lo+hi)//2 if x < key(a[mid]): hi = mid else: lo = mid+1 return lo def bisect_search(a, x, lo=0, hi=None, key=None): if not key: def key(x): return x index = bisect_right(a, x, lo, hi, key) if index == 0: return -1 else: searched = a[index-1] if key(searched) == x: return index-1 else: return -1 ``` 示例： ``` s = [ { "id":10, "name":"pig" }, { "id":11, "name":"superpig" }, ] index = bisect_search(s, 10, key=lambda x:x.get("id")) ``` 来自 大脸猫 写于 2018-10-17 10:49 -- 更新于2023-03-21 16:07 -- 2 条评论