Python二分查找算法与bisect模块实战指南

慢慢来

发布时间：2026-10-13 | 1人浏览过

原创

本文深入解析Python中二分查找算法的原理与实现，对比递归与循环方式的性能差异。重点介绍bisect模块如何高效维护有序列表，并详细对比其与numpy.searchsorted在普通列表与大型数组场景下的执行效率，为开发者提供实用的性能优化建议。

前言

Python的列表（list）底层基于数组实现，属于线性表结构。若需查找列表中的特定元素，可直接调用 list.index() 方法，但该操作的时间复杂度为O(n)。当数据量庞大时，采用二分查找算法可显著提升查询效率。

二分查找的前提条件是目标对象必须保持有序状态，其核心逻辑如下：

1. 首先定位数组的中间元素，若该元素即为目标值，则查找结束；

2. 若目标值大于或小于中间元素，则仅在大于或小于中间元素的那一半区间内继续查找，且比较方式与起始步骤一致；

3. 若在某次迭代中区间为空，则判定目标值不存在。

二分查找亦称折半查找，每次比较均能将搜索范围缩减一半，因此其时间复杂度为 O(logn)。

下面分别通过递归和循环两种方式实现二分查找：

def binary_search_recursion(lst, value, low, high): 
 if high < low: 
 return None
 mid = (low + high) / 2 
 if lst[mid] > value: 
 return binary_search_recursion(lst, value, low, mid-1) 
 elif lst[mid] < value: 
 return binary_search_recursion(lst, value, mid+1, high) 
 else: 
 return mid 

def binary_search_loop(lst,value): 
 low, high = 0, len(lst)-1 
 while low <= high: 
 mid = (low + high) / 2 
 if lst[mid] < value: 
 low = mid + 1 
 elif lst[mid] > value: 
 high = mid - 1
 else:
 return mid 
 return None

随后对这两种实现方式进行性能基准测试：

if __name__ == "__main__":
 import random
 lst = [random.randint(0, 10000) for _ in xrange(100000)]
 lst.sort()

 def test_recursion():
 binary_search_recursion(lst, 999, 0, len(lst)-1)

 def test_loop():
 binary_search_loop(lst, 999)

 import timeit
 t1 = timeit.Timer("test_recursion()", setup="from __main__ import test_recursion")
 t2 = timeit.Timer("test_loop()", setup="from __main__ import test_loop")

 print "Recursion:", t1.timeit()
 print "Loop:", t2.timeit()

测试结果如下：

Recursion: 3.12596702576
Loop: 2.08254289627

数据显示，循环实现的效率高于递归实现。

bisect 模块

Python内置的 bisect 模块专门用于维护有序列表。该模块提供了一套基于二分法的算法，用于将元素高效插入有序列表。在某些场景下，直接利用 bisect 插入比反复调用列表排序方法或构建大列表后统一排序更为高效。Bisect 意为二分法，此处指利用二分查找定位插入点，从而避免每次调用 sort 来维持列表有序性。

以下是一个基础使用示例：

import bisect
import random

random.seed(1)

print'New Pos Contents'
print'--- --- --------'

l = []
for i in range(1, 15):
 r = random.randint(1, 100)
 position = bisect.bisect(l, r)
 bisect.insort(l, r)
 print'%3d %3d' % (r, position), l

输出结果：

New Pos Contents
--- --- --------
 14 0 [14]
 85 1 [14, 85]
 77 1 [14, 77, 85]
 26 1 [14, 26, 77, 85]
 50 2 [14, 26, 50, 77, 85]
 45 2 [14, 26, 45, 50, 77, 85]
 66 4 [14, 26, 45, 50, 66, 77, 85]
 79 6 [14, 26, 45, 50, 66, 77, 79, 85]
 10 0 [10, 14, 26, 45, 50, 66, 77, 79, 85]
 3 0 [3, 10, 14, 26, 45, 50, 66, 77, 79, 85]
 84 9 [3, 10, 14, 26, 45, 50, 66, 77, 79, 84, 85]
 44 4 [3, 10, 14, 26, 44, 45, 50, 66, 77, 79, 84, 85]
 77 9 [3, 10, 14, 26, 44, 45, 50, 66, 77, 77, 79, 84, 85]
 1 0 [1, 3, 10, 14, 26, 44, 45, 50, 66, 77, 77, 79, 84, 85]

Bisect模块主要提供以下函数：

bisect.bisect_left(a,x, lo=0, hi=len(a)) :

查找在有序列表 a 中插入 x 的索引位置。参数 lo 和 hi 用于限定查找区间，默认覆盖整个列表。若 x 已存在，则返回其左侧的插入点。返回值为索引 index。

bisect.bisect_right(a,x, lo=0, hi=len(a))

bisect.bisect(a, x,lo=0, hi=len(a)) ：

这两个函数行为与 bisect_left 类似，区别在于若 x 已存在，则返回其右侧的插入点。

bisect.insort_left(a,x, lo=0, hi=len(a)) ：

在有序列表 a 中实际插入元素 x。其效果等同于执行 a.insert(bisect.bisect_left(a,x, lo, hi), x)。

bisect.insort_right(a,x, lo=0, hi=len(a))

bisect.insort(a, x,lo=0, hi=len(a)) :

行为与 insort_left 类似，但若 x 已存在，则在其右侧进行插入。

Bisect模块提供的函数可分为两类：bisect* 系列仅用于查找插入索引，不执行实际插入操作；而 insort* 系列则负责执行实际的列表插入。

该模块的一个典型应用场景是计算分数等级：

def grade(score,breakpoints=[60, 70, 80, 90], grades='FDCBA'):
 i = bisect.bisect(breakpoints, score)
 return grades[i]

print [grade(score) for score in [33, 99, 77, 70, 89, 90, 100]]

执行结果：

['F', 'A', 'C', 'C', 'B', 'A', 'A']

同样，我们可以利用 bisect 模块来实现二分查找功能：

def binary_search_bisect(lst, x):
 from bisect import bisect_left
 i = bisect_left(lst, x)
 if i != len(lst) and lst[i] == x:
 return i
 return None

接下来测试其与前述递归和循环实现方式的性能对比：

Recursion: 4.00940990448
Loop: 2.6583480835
Bisect: 1.74922895432

结果显示，bisect 的实现速度略快于纯循环实现，而比递归实现快约一倍。

Python著名的数据处理库 numpy 也提供了用于二分查找的函数 numpy.searchsorted，其用法与 bisect 基本一致。不同之处在于，若需指定在右侧插入，必须设置参数 side='right'，例如：

>>> import numpy as np
>>> from bisect import bisect_left, bisect_right
>>> data = [2, 4, 7, 9]
>>> bisect_left(data, 4)
1
>>> np.searchsorted(data, 4)
1
>>> bisect_right(data, 4)
2
>>> np.searchsorted(data, 4, side='right')
2

我们再次进行性能对比：

In [20]: %timeit -n 100 bisect_left(data, 99999)
100 loops, best of 3: 670 ns per loop

In [21]: %timeit -n 100 np.searchsorted(data, 99999)
100 loops, best of 3: 56.9 ms per loop

In [22]: %timeit -n 100 bisect_left(data, 8888)
100 loops, best of 3: 961 ns per loop

In [23]: %timeit -n 100 np.searchsorted(data, 8888)
100 loops, best of 3: 57.6 ms per loop

In [24]: %timeit -n 100 bisect_left(data, 777777)
100 loops, best of 3: 670 ns per loop

In [25]: %timeit -n 100 np.searchsorted(data, 777777)
100 loops, best of 3: 58.4 ms per loop

结果表明，numpy.searchsorted 在普通列表上的效率较低，与 bisect 模块不在同一数量级。因此，searchsorted 并不适合用于普通数组的搜索，但在处理 numpy.ndarray 时速度极快：

In [30]: data_ndarray = np.arange(0, 1000000)

In [31]: %timeit np.searchsorted(data_ndarray, 99999)
The slowest run took 16.04 times longer than the fastest. This could mean that an intermediate result is being cached.
1000000 loops, best of 3: 996 ns per loop

In [32]: %timeit np.searchsorted(data_ndarray, 8888)
The slowest run took 18.22 times longer than the fastest. This could mean that an intermediate result is being cached.
1000000 loops, best of 3: 994 ns per loop

In [33]: %timeit np.searchsorted(data_ndarray, 777777)
The slowest run took 31.32 times longer than the fastest. This could mean that an intermediate result is being cached.
1000000 loops, best of 3: 990 ns per loop

numpy.searchsorted 支持同时搜索多个值：

>>> np.searchsorted([1,2,3,4,5], 3)
2
>>> np.searchsorted([1,2,3,4,5], 3, side='right')
3
>>> np.searchsorted([1,2,3,4,5], [-10, 10, 2, 3])
array([0, 5, 1, 2])

总结

以上就是本文的全部内容，希望这些内容能对大家学习或使用Python有所帮助。如有任何疑问，欢迎留言交流。