利用Bisect模块，实现高效优雅的二分搜索

学过算法的同学都熟悉二分法算法，二分法又叫折半算法，是一种高效的搜索算法。以二分法为基础的一些衍生算法是构成现代软件的基础之一，比如Mysql底层用的B树。在Python中也有一个非常简单方便的二分发模块bisect，该模块很简单，只有两个函数，但是大有用途。本文虫虫给大家介绍一些bisect模块的妙用，比如高效搜索数据、对任何数据进行排序等等。

概述

bisect是一个基本的二分算法，将给定的曲线、图形或区间分成两个相等的部分（两半）。简而言之，就是用折半搜索。

二分法，是一个高效算法。二分搜索的有着O(log(n))时间复杂度的效率，这是除了常数算法外，能达到的最快的算法了。

Python的bisect模块很简单，只有两个函数bisect_left() 和bisect_right()（实际上，多数情况下仅用到bisect_left）。

比如，对一个列表：

import bisectsome_list = [0, 6, 1, 5, 8, 2]some_list.sort()print(some_list) # [0, 1, 2, 5, 6, 8]i = bisect.bisect_left(some_list, 4)print(i) # 3some_list.insert(i, 4)print(some_list) # [0, 1, 2, 4, 5, 6, 8]# 或者bisect.insort_left(some_list, 4)print(some_list) # [0, 1, 2, 4, 5, 6, 8]

在这个示例代码中，首先对列表进行排序，对于一个排序好的列表，只能用bisect函数。使用bisect_left在排序列表中查找第二个参数(4)的索引。然后继续。插入数字4在索引3处（上一部中找到的索引位置）。也可以直接使用insort_left（其内部也使用bisect_left）实现操作。

二分查找

bisect主要的功能就是二分搜索：

from bisect import bisect_leftdef binary_search(a, x, lo=0, hi=None):if hi is None:hi = len(a)pos = bisect_left(a, x, lo, hi) # 搜索插入位置return pos if pos != hi and a[pos] == x else -1print(binary_search([0, 1, 2, 5, 6, 8], 5)) # 3print(binary_search([0, 1, 2, 5, 6, 8], 4)) # -1

实现一个binary_search函数，函数遵循bisect模块中的函数相同的模式。寻找价值x在列表a中lo和hi之间的索引。

return语句，其中测试该值是否x实际上在列表中，如果是则返回其位置，否则返回-1。

寻找重复值

bisect模块可以做其他有趣的功能，比如在列表中查找连续的相等值：

from bisect import bisect_left, bisect_rightsome_list = [5, 10, 15, 15, 15, 20, 25, 40]# Find all the 15'svalue = 15start = bisect_left(some_list, value)end = bisect_right(some_list, value)print(f'Successive values of {value} from index {start} to {end}: {some_list[start:end]}')# Successive values of 15 from index 2 to 5: [15, 15, 15]

bisect_left函数上面介绍过，还有一个bisect模块中唯二的函数之一bisect_right大概做差不多一样的搜索，但是返回搜索位置最右边的索引。结合两个函数就可以找到连续重复值值的开始和结束位置。

区间映射到值

假设有一系列间隔/范围，想要返回相应的值。用if-elif可以实现，比较繁琐，难看：

def interval_to_value(val):if val return 0elif 100 < val return 1elif 300 < val return 2elif 500 < val return 3elif 800 < val return 4elif val > 1000:return 5

更优雅的方法是使用bisect_left:

def interval_to_value(val):return bisect_left([100, 300, 500, 800, 1000], val)

另外这个方法不仅优雅，由于使用的是二分法，效率很高，速度非常快。

有了这个函数，就可以这样花式调用：

i = interval_to_value(369)a = ['absent', 'low', 'average', 'high', 'very high', 'extreme']print(a[i]) # average

字典近似键

假设有一个字典形式的映射，现在想要查找指定键的值。如果该键存在,就直接输出，如果不存在，就返回最接近的键的值：

import collectionssome_dict = collections.OrderedDict([(0, 0), (2, 1), (4, 4), (6, 9), (8, 16), (10, 25), (12, 36), (14, 49), (16, 64), (18, 81)])target = 10.5index = bisect_left(list(some_dict.keys()), target) # 6items = list(some_dict.items())distance1= some_dict.keys()[index]-targetdistance2= target-some_dict.keys()[index-1]# Check which one is closer:print(f'Distance for to index {index}: {distance1}') # Distance for to index 5: 1.5print(f'Distance for to index {index-1}: {distance2}') # Distance for to index 6: 0.5print('Closest value:')if distance1 < distance2:print(items[index])else:print(items[index-1])# Closest value: (10, 25)

此处使用OrderedDict确保键的顺序正确。然后使用bisect_left找到插入点。 最后，需要检查下一个或上一个索引是否更接近target。

前缀搜索

用bisect也可以实现前缀搜索。假设有一个非常大的单词列表，并且想要根据给定的前缀查找单词：

def prefix_search(wordlist, prefix):try:index = bisect_left(wordlist, prefix)return wordlist[index].startswith(prefix)except IndexError:return Falsewords = ['another', 'data', 'date', 'hello', 'text', 'word']print(prefix_search(words, 'dat')) # Trueprint(prefix_search(words, 'xy')) # False

上面的函数仅检查列表中是否存在具有指定前缀的单词，但这可以很容易地修改为返回所有以prefix开头的位置。

对一个和大的单词列表，使用bisect要快得多。

自定义对象排序

到目前为止，只使用了内置类型，bisect模块也可以应用于自定义类型。假设有一个自定义对象列表，现在希望根据某些属性维护它们在列表中的顺序：

from bisect import insort_leftclass CustomObject:def __init__(self, val):self.prop = val # The value to comparedef __lt__(self, other):return self.prop < other.propdef __repr__(self):return 'CustomObject({})'.format(self.prop)some_objects = sorted([CustomObject(7), CustomObject(1), CustomObject(3), CustomObject(9)])insort_left(some_objects, CustomObject(2))print(some_objects)# [CustomObject(1), CustomObject(2), CustomObject(3), CustomObject(7), CustomObject(9)]

该代码片段中：将bisec用于比较对象自定义的魔术方法__lt__。

函数式

bisect模块还支持使用更复杂的比较/搜索，key函数式（lambda）参数用法：

some_list = [1, 3, 7, 16, 25]some_list.reverse()insort_left(some_list, 10, key=lambda x: -1 * x)print(some_list) # [25, 16, 10, 7, 3, 1]

这里我们使用key函数来实现逆序二分搜索，只需记住列表也必须首先以逆序排序。

与逆序排序类似，也可以用key函数来搜索元组列表：

list_of_tuples = [(1, 3), (3, 8), (5, 4), (10, 12)]index = bisect_left(list_of_tuples, (5, )) # 2print(list_of_tuples[2]) # (5, 4)

省略tuple中的第二个的值，根据其第一个值进行比较。也可以显式指定key=lambda i: i[0]也是oK的。

但是key的函数式这样的写法，多少有点不是很直观易懂。我们更希望是像sorted一样直观地写法：

some_tuples = [(0, 10),(2, 12),(3, 15),(5, 20),]print(sorted(some_tuples, key=lambda t: t[0] + t[1]))

但bisect_left不支持：

index = bisect_left(some_tuples, (4, 17), key=lambda t: t[0] + t[1]) #报错# Expectation: index = 3# Reality: "TypeError: '

对于这种写法，必须先定义一个key函数，将其作为key参数并在第二个参数上调用它：

def key_func(t):return t[0] + t[1]index = bisect_left(some_tuples, key_func((4, 17)), key=key_func)print(index) # 3

略显繁琐。

总结

一个小小的模块可以做大大的用途。实际上编程就是这样，通过挖掘简单的功能，善用之，就可以高效的解决实际的问题。

关于bisect，实际上熟悉git的人都知道，git其实也有这样一个子功能，用来快速找到真正导致问题的那次提交，从而找到问题所在。

Bisect是一个非常高效快捷，得益于，其底层二分算法的高性能。二分搜索的时间复杂度为O(log(n))，这基本上是最快的算法了。