python中的bisect模块与二分查找

1.bisect模块概述

bisect是python的内置模块, 用于有序序列的插入和查找。 插入的数据不会影响列表的排序, 但是原有列表需要是有序的, 并且不能是倒序.

Bisect模块提供的函数有：

• bisect.bisect_left(a,x, lo=0, hi=len(a))
• bisect.bisect_right(a,x, lo=0, hi=len(a))
• bisect.bisect(a, x,lo=0, hi=len(a))
• bisect.insort_left(a,x, lo=0, hi=len(a))
• bisect.insort_right(a,x, lo=0, hi=len(a))
• bisect.insort(a, x,lo=0, hi=len(a))

2.bisect模块的函数详解

2.1 bisect.bisect*()方法

• bisect.bisect_left(a,x,lo=0,hi=len(a),*,key=None)

在有序数组a中[lo,hi]区间内查找x插入的位置，返回的是索引值。如果a中有跟x相同的元素，则x插入的位置是左边，key指定了一个单参数的方法，该方法的返回值作为与k比较的基准。

值得注意的是,key参数是3.10版本以后才添加的功能。

• bisect.bisect_right(a,x,lo=0,hi=len(a),*,key=None)，在有序数组a中[lo,hi]区间内查找x插入的位置，返回索引值。如果a中有跟x相同的元素，则x插入的位置是右边。
• bisect.bisect(a,x,lo=0,hi=len(a),*,key=None)，同bisect_right

# bisect_left Vs. bisect (bisect_right)
import bisect

nums = [1, 2, 2, 4]
i, j = bisect.bisect_left(nums, 2), bisect.bisect(nums, 2)
print(i)  # 输出1
print(j)  # 输出3
1
2
3
4
5
6
7

可见，针对上面给出的数组，想要插入2，使用bisect_left返回的索引值是1，使用bisect(bisect_right)返回的索引值是3。如果指定了lo和hi的话，那么返回的就是在这个范围内的索引。如下面的例子所示。

# 指定lo和hi
import bisect

nums = [1, 2, 2, 2, 2, 4]
i = bisect.bisect_left(nums, 2, 3)
print(i)  # 输出为3
1
2
3
4
5
6

如果不指定lo=3的话，返回的索引应该是1。指定lo=3后，返回的索引为3。

关键字key指定了一个方法，这个方法会接受当前数组中的中间值mid（因为二分查找就是从中间值开始的）作为其参数，然后返回一个值val，val用于跟x比较。

# 指定key值
import bisect

nums = [1, 2, 3, 4, 6, 8]


def divide(mid):
    print('mid: ' + str(mid))
    return mid // 2


i = bisect.bisect_left(nums, 5, key=divide)
print(i)
1
2
3
4
5
6
7
8
9
10
11
12
13

上面的例子中定义了一个divide方法。那么bisect_left方法的执行顺序是这样的：

1. nums中的中间值mid=4, divide(mid)方法返回值为2

2. 5>2,则查找nums的右子数组，即[6,8]

3. [6,8]的中间值是mid=8, divide(mid)方法返回值为4

4. 5>4，则继续查找右子数组，可是已经没有右子数组了，则返回索引值为6.

2.2 bisect.insort*()方法

• bisect.insort_left(a,x,lo=0,hi=len(a),*,key=None)，在有序数组a中[lo,hi]区间内查找x插入的位置，返回的是索引值。如果a中有跟x相同的元素，则x插入的位置是最左边，key指定了一个单参数的方法，该方法的返回值作为与k比较的基准。

• bisect.insort_right(a,x,lo=0,hi=len(a),*,key=None)，在有序数组a中[lo,hi]区间内查找x插入的位置，返回索引值。如果a中有跟x相同的元素，则x插入的位置是最右边。

• bisect.insort(a,x,lo=0,hi=len(a),*,key=None)，同insort_right。

# bisect.insort_left
import bisect

nums = [1, 2, 3, 4, 6, 8]
bisect.insort_left(nums, 5)
print(nums)
# [1, 2, 3, 4, 5, 6, 8]
1
2
3
4
5
6
7

值得注意的是，insort方法中的key和bisect方法中的key指定的方法针对的对象是不同的。

# bisect.insort_left with key
import bisect

nums = [1, 2, 3, 4, 6, 8]


def divide(mid):
    print('mid: ' + str(mid))
    return mid // 2


bisect.insort_left(nums, 5, key=divide)
1
2
3
4
5
6
7
8
9
10
11
12

可见，key指定的方法的参数是针对x的。也就是说insort_left方法的执行顺序是这样的：

1. mid=x=5，返回的值是2，也就是divide(x)

2. mid是数组的中间值，即mid=4, divide方法返回的值是2

3. divide(x)==2，则查找左子数组

4. 中间值为2，mid=2, divide方法返回的值是1

5. divide(x)>1，则查找右子数组

6. 中间值为3，mid=3, divide方法的返回值是1

7. divide(x)>1，则查找右子数组

8. 没有右子数组了，则插入位置的索引为3

得到了插入5之后的数组为[1,2,3,5,4,6,8]

3.python中的二分查找

3.1 标准的二分查找

class BinarySearch:
    # 标准的二分查找，找不到返回-1
    def binsearch(self, nums, target):
        lo, hi = 0, len(nums) - 1
        while lo <= hi:
            mid = lo + (hi - lo) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] > target:
                hi = mid - 1
            else:  # nums[mid] < target:
                lo = mid + 1
        return -1
1
2
3
4
5
6
7
8
9
10
11
12
13

3.2 查找第一个>=target的元素索引

class BinarySearch:
    # 查找第一个>=target的元素索引，找不到返回数组长度
    def lowerbound(self, nums, target):
        lo, hi = 0, len(nums) - 1
        pos = len(nums)  # 找不到
        while lo < hi:
            mid = lo + (hi - lo) // 2
            if nums[mid] >= target:
                hi = mid
            else:  # nums[mid] < target:
                lo = mid + 1
        if nums[lo] >= target:  # lo:要找的元素索引
            pos = lo
        return pos
1
2
3
4
5
6
7
8
9
10
11
12
13
14

3.3 查找第一个>target的元素索引

class BinarySearch:
    # 查找第一个>target的元素索引，找不到返回数组长度
    def upperbound(self, nums, target):
        lo, hi = 0, len(nums) - 1
        pos = len(nums)  # 找不到
        while lo < hi:
            mid = lo + (hi - lo) // 2
            if nums[mid] > target:
                hi = mid
            else:  # nums[mid] <= target:
                lo = mid + 1
        if nums[lo] > target:  # lo:要找的元素索引
            pos = lo
        return pos
1
2
3
4
5
6
7
8
9
10
11
12
13
14

4.二分查找的变形与 bisect 模块的关系

• 二分查找中的 lowerbound(nums, target) 等价于 bisect.bisect_left(a,x, lo=0, hi=len(a))
• 二分查找中的upperbound(nums, target) 等价于 bisect.bisect_right(a,x, lo=0, hi=len(a)) 或者bisect.bisect(a,x, lo=0, hi=len(a))

参考:

1.https://www.cnblogs.com/larissa-0464/p/16379684.html

2.https://cloud.tencent.com/developer/article/1536426