使用排序列表有时可能有点棘手。您需要在每次插入后维护列表的顺序并有效地搜索其中的元素。二分搜索是一种用于在排序列表中搜索的强大算法。虽然从头开始实施并不太困难，但可能非常耗时。幸运的是，Python 提供了 bisect 模块，这使得处理排序列表变得更加容易。

什么是二分查找？

二分搜索是一种在排序数组中查找目标值位置的算法。想象一下您正在电话簿中搜索一个名字。您可能不是从第一页开始，而是从书的中间开始，并根据名称按字母顺序是大于还是小于中间的名称来决定是在前半部分还是后半部分继续搜索。二分查找以类似的方式进行操作：它以两个指针开始，一个位于列表的开头，另一个位于列表的末尾。然后计算中间元素并与目标进行比较。

bisect 模块：简化排序列表操作

虽然二分查找很有效，但每次都写出实现可能很乏味。但是，如果您只需一行代码即可执行相同的操作呢？这就是 Python 的 bisect 模块的用武之地。bisect 是 Python 标准库的一部分，可帮助您维护排序列表，而无需在每次插入后对其进行排序。它使用简单的二分算法来实现这一点。

bisect 模块提供两个关键函数：bisect 和 insort。 bisect 函数查找应插入元素以保持列表排序的索引，而 insort 则将元素插入到列表中同时保持其排序顺序。

使用二等分模块：一个实际示例

让我们从导入模块开始：

import bisect

示例 1：将数字插入排序列表

假设我们有一个已排序的数字列表：

data = [1, 3, 5, 6, 8]

要在保持列表排序的同时插入新数字，只需使用：

bisect.insort(data, 7)

运行此代码后，数据将如下所示：

[1, 3, 5, 6, 7, 8]

示例 2：查找插入点

如果您只想找出数字将插入的位置而不实际插入数字怎么办？您可以使用 bisect_left 或 bisect_right 函数：

index = bisect.bisect_left(data, 4)
print(index)  # Output: 2

这告诉我们应该将数字 4 插入到索引 2 处以保持列表排序。

示例 3：维护动态列表中的排序顺序

假设您正在管理一个动态增长的列表，需要插入元素，同时确保其保持排序：

dynamic_data = []
for number in [10, 3, 7, 5, 8, 2]:
    bisect.insort(dynamic_data, number)
    print(dynamic_data)

这将在插入元素时输出每一步的列表：

[10]
[3, 10]
[3, 7, 10]
[3, 5, 7, 10]
[3, 5, 7, 8, 10]
[2, 3, 5, 7, 8, 10]

示例 4：将 bisect 与自定义对象结合使用

假设您有一个自定义对象列表，例如元组，并且您想根据特定条件插入它们：

items = [(1, 'apple'), (3, 'cherry'), (5, 'date')]
bisect.insort(items, (2, 'banana'))
print(items)  # Output: [(1, 'apple'), (2, 'banana'), (3, 'cherry'), (5, 'date')]

或者您可能想根据每个元组的第二个元素插入：

items = [('a', 10), ('b', 20), ('c', 30)]
bisect.insort(items, ('d', 25), key=lambda x: x[1])
print(items)  # Output: [('a', 10), ('b', 20), ('d', 25), ('c', 30)]

行动中的二分法：搜索单词

二等分模块不限于数字；它对于搜索字符串、元组、字符等列表也很有用。
例如，要在排序列表中查找单词：

def searchWord(dictionary, target):
    return bisect.bisect_left(dictionary, target)


dictionary = ['alphabet', 'bear', 'car', 'density', 'epic', 'fear', 'guitar', 'happiness', 'ice', 'joke']
target = 'guitar'

或者查找具有特定前缀的单词组中的第一个单词：

def searchPrefix(dictionary, prefix):
    return bisect.bisect_left(dictionary, prefix), bisect.bisect_right(dictionary, prefix   'z') # adding 'z' to the prefix to get the last word starting with the prefix
# bisect_rigth function will be discussed in a moment


dictionary = ['alphabet', 'bear', 'car', 'density', 'epic', 'fear', 'generator', 'genetic', 'genius', 'gentlemen', 'guitar', 'happiness', 'ice', 'joke']
prefix = 'gen'

但是，请记住 bisect_left 返回应插入目标的索引，而不是目标是否存在于列表中。

bisect 和 insort 的变体

该模块还包括右侧变体：bisect_right 和 insort_right。如果元素已在列表中，这些函数将返回插入元素的最右侧索引。例如，如果目标在列表中，bisect_right 将返回大于目标的第一个元素的索引，而 insort_right 在该位置插入元素。

引擎盖下平分

bisect 模块的强大之处在于它有效地实现了二分搜索算法。例如，当您调用 bisect.bisect_left 时，该函数实质上对列表执行二分搜索以确定新元素的正确插入点。

下面是它的工作原理：

1. 初始化：函数以两个指针lo和hi开始，分别代表列表内搜索范围的下限和上限。最初，lo 设置为列表的开头（索引 0），hi 设置为列表的末尾（索引等于列表的长度）。但您也可以指定自定义 lo 和 hi 值以在列表的特定范围内进行搜索。

2. Bisection：在循环内，该函数计算 lo 和 hi 之间的中点 (mid)。然后它将中间的值与您要插入的目标值进行比较。

3. 比较：

* If the target is less than or equal to the value at `mid`, the upper bound (`hi`) is moved to `mid`.
* If the target is greater, the lower bound (`lo`) is moved to `mid   1`.

1. 终止：这个过程继续进行，每次将搜索范围减半，直到lo等于hi。此时，lo（或 hi）表示应将目标插入其中以维持列表排序顺序的正确索引。

2. 插入：对于 insort 函数，一旦使用 bisect_left 找到正确的索引，目标就会被插入到列表中的该位置。

这种方法确保插入过程高效，由于列表移位操作，搜索的时间复杂度为 O(log n)，插入的时间复杂度为 O(n)。这比每次插入后对列表进行排序要高效得多，特别是对于大型数据集。

bisect_left 代码示例：

    if lo 



insort_left 代码示例：



def insort_left(a, x, lo=0, hi=None, *, key=None):

    if key is None:
        lo = bisect_left(a, x, lo, hi)
    else:
        lo = bisect_left(a, key(x), lo, hi, key=key)
    a.insert(lo, x)





  
  
  结论


bisect 模块使排序列表的处理变得简单而高效。下次您需要执行二分搜索或将元素插入排序列表时，请记住二等分模块，这样可以节省时间和精力。