Python bisect模块原理及常见实例-猿码集

1. Python bisect模块概述

Python中的bisect模块主要用于二分查找，即在一个有序的列表中查找指定的元素。bisect模块提供的函数可以帮助我们在包含数值的序列中查找元素的位置，可以用于搜索特定元素、插入元素到序列中以及实现其他的操作。

2. bisect模块函数

2.1 bisect_left函数

该函数用于查找指定元素在有序列表中应该插入的位置，返回值是应该插入的位置（也就是说，如果列表中已经有了该元素的话，那么返回该元素在列表中的位置）。

示例：


import bisect
a = [1, 3, 4, 4, 6]
x = 4
location = bisect.bisect_left(a, x)
print(location)     # 输出2

2.2 bisect_right函数

该函数也用于查找指定元素在有序列表中应该插入的位置，不同之处在于，如果列表中已经有了该元素的话，那么返回该元素在列表中右侧的位置。

示例：


import bisect
a = [1, 3, 4, 4, 6]
x = 4
location = bisect.bisect_right(a, x)
print(location)     # 输出4

2.3 insort_left函数

该函数用于往有序列表中插入元素，并保持列表的有序性。

示例：


import bisect
a = [1, 3, 4, 4, 6]
x = 5
bisect.insort_left(a, x)
print(a)    # 输出[1, 3, 4, 4, 5, 6]

2.4 insort_right函数

该函数也用于往有序列表中插入元素，并保持列表的有序性，不同之处在于插入的位置。

示例：


import bisect
a = [1, 3, 4, 4, 6]
x = 5
bisect.insort_right(a, x)
print(a)    # 输出[1, 3, 4, 4, 5, 6]

3. bisect模块实例

3.1 查找列表中的最大值或最小值

有时候我们需要从一个有序的列表中查询最大值或者最小值，可以使用bisect_left函数或bisect_right函数来完成。

示例：


import bisect
a = [1, 3, 4, 4, 6]
# 查找最小值
min_value = a[bisect.bisect_left(a, a[0])]
print(min_value)     # 输出1
# 查找最大值
max_value = a[bisect.bisect_right(a, a[-1])-1]
print(max_value)     # 输出6

3.2 查找数字在有序列表中的位置

有时候我们需要查找一个数字在有序列表中的位置，可以使用bisect_left函数或bisect_right函数来进行查找。

示例：


import bisect
a = [1, 3, 4, 4, 6]
x = 4
location = bisect.bisect_left(a, x)
if location < len(a) and a[location] == x:
    print(location)     # 输出2
else:
    print('Not found')

3.3 查找数字在有序列表中的出现次数

有时候我们需要查找一个数字在有序列表中的出现次数，可以通过计算该数字在列表中出现的次数来实现。

示例：


import bisect
a = [1, 3, 4, 4, 6]
x = 4
left = bisect.bisect_left(a, x)
right = bisect.bisect_right(a, x)
if right - left > 0:
    print('出现了{}次'.format(right - left))
else:
    print('未出现')

3.4 实现sortedcontainers模块中的SortedDict类

SortedDict是一个基于bisect模块的有序字典实现，可以在我们需要将键值对按照键的大小进行排序的时候使用。

实现代码：


import bisect
class SortedDict:
    def __init__(self, items=None):
        self.keys = []
        self.values = []
        if items:
            for k, v in items:
                self[k] = v
    def __setitem__(self, key, value):
        i = bisect.bisect_left(self.keys, key)
        if i < len(self.keys) and self.keys[i] == key:
            self.values[i] = value
        else:
            self.keys.insert(i, key)
            self.values.insert(i, value)
    def __getitem__(self, key):
        i = bisect.bisect_left(self.keys, key)
        if i < len(self.keys) and self.keys[i] == key:
            return self.values[i]
        else:
            raise KeyError(key)
    def __len__(self):
        return len(self.keys)
    def __repr__(self):
        return '{}({})'.format(self.__class__.__name__, list(self.items()))
    def items(self):
        return zip(self.keys, self.values)

4. 总结

Python的bisect模块提供了一些有用的函数来操作有序列表，包括查找元素的位置和向列表中插入元素等。使用bisect模块可以简化代码，提高效率。

Python bisect模块原理及常见实例