bisect left - Alexander Lee

速记总结#

找 “第一个 >= x”#

1
i = bisect_left(a, x)
2
if i < len(a):
3
    ans = a[i]   # 第一个 >= x

找 “最后一个 < x”#

1
i = bisect_left(a, x)
2
if i > 0:
3
    ans = a[i-1]  # 最后一个 < x

（在 Heaters 里就是左边最近的 heater）

判断 x 是否存在于数组中#

1
i = bisect_left(a, x)
2
exists = (i < len(a) and a[i] == x)

找 “x 应该插入的位置”#

1
pos = bisect_left(a, x)

插入到 pos 可以保持有序（并且插到同值最左边）

找 “小于 x 的元素个数”#

1
count = bisect_left(a, x)

因为 i 左边全是 < x 的。

找 “>= x 的元素个数”#

1
count = len(a) - bisect_left(a, x)

Example#

r = len(nums) - 1 # 记得减1

1
import bisect as b
2

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

5
# 第一个 >= x 的位置
6
a = b.bisect_left(nums, 2)
7
print(a) # 1
8

9
def find_bisect_left(nums, k):
10
    l = 0
11
    r = len(nums) - 1 # 记得减1
12
    while l <= r:
13
        m = (l + r) // 2
14
        if nums[m] >= k:
15
            r = m - 1
16
        else:
17
            l = m + 1
18
    return l
19

20
print(find_bisect_left(nums, 2))
21

22

23
# 第一个 > x 的位置
24
a = b.bisect(nums, 2)
25
print(a) # 3
26
a = b.bisect_right(nums, 2)
27
print(a) # 4
28

29
def find_bisect_right(nums, k):
30
    l = 0
31
    r = len(nums) - 1
32
    while l <= r:
33
        m = (l + r) // 2
34
        if nums[m] > k:
35
            r = m - 1
36
        else:
37
            l = m + 1
38
    return l
39

40
print(find_bisect_right(nums, 2))