盛日辉的博客
0%

二分查找

发表于 更新于 分类于

记录一下抠二分查找细节的过程。

// 运算符

是除了之后向下取整。

1
2
3
4
5
6
7
8
9
10
11
12
5//2
Out[2]: 2
12//5
Out[3]: 2
14//5
Out[4]: 2
1//2
Out[5]: 0
-1//2
Out[6]: -1
(-1)//2
Out[7]: -1

对于(left+right)//2来说，奇数个就正好是中间，偶数个会更靠近left一些。

关于区间的讨论

左闭右闭

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def search(arr, x):
    left = 0
    right = len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        print(left, mid, right)
        if arr[mid] < x:
            left = mid + 1
        elif arr[mid] > x:
            right = mid - 1
        else:
            break
    print(left, mid, right)


if __name__ == '__main__':
    a = [0, 1, 2, 3, 4, 5, 6]
    x = 5
    print(a)
    for i in a:
        print("===================================")
        print("x =",i)
        search(a, i)

输出结果：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
[0, 1, 2, 3, 4, 5, 6]
===================================
x = 0
0 3 6
0 1 2
0 0 0
0 0 0
===================================
x = 1
0 3 6
0 1 2
0 1 2
===================================
x = 2
0 3 6
0 1 2
2 2 2
2 2 2
===================================
x = 3
0 3 6
0 3 6
===================================
x = 4
0 3 6
4 5 6
4 4 4
4 4 4
===================================
x = 5
0 3 6
4 5 6
4 5 6
===================================
x = 6
0 3 6
4 5 6
6 6 6
6 6 6

因为当arr[mid] == x的时候，break了循环，所以最终如果要查找的数在数组中，mid就是结果的位置，如果不在（改了一下输出）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
[0, 1, 2, 3, 5, 6]
===================================
x = 18
left:0, mid:2, right:5
left:3, mid:4, right:5
left:5, mid:5, right:5
循环结束，left:6, mid:5, right:5
===================================
x = 4
left:0, mid:2, right:5
left:3, mid:4, right:5
left:3, mid:3, right:3
循环结束，left:4, mid:3, right:3
===================================
x = -1
left:0, mid:2, right:5
left:0, mid:0, right:1
循环结束，left:0, mid:0, right:-1
  • 退出循环后，left指向的是x应该在的位置
  • 在退出循环的前一步，left和rignt会指向同一个位置，那mid也是
    • 如果arr[mid] < x，x应当在当前位置的右边，移动left，这时候left就是x该在的位置；
    • 如果arr[mid] > x，x比左边的数大比右边的小，所以left就是x该在的位置，移动right后退出循环;
如果没有单独的else即arr[mid] == x这一分支呢？

将等于加到大于上：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def search(arr, x):
    print("===================================")
    print("x =", x)
    left = 0
    right = len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        print(f"left:{left}, mid:{mid}, right:{right}")
        if arr[mid] < x:
            left = mid + 1
        elif arr[mid] >= x:
            right = mid - 1
        # else:
        #     break
    print(f"循环结束，left:{left}, mid:{mid}, right:{right}")


if __name__ == '__main__':
    a = [0, 2, 4,  6]
    x = 5
    print(a)
    for i in a:
        search(a, i)
    search(a, 1)
    search(a, 5)
    search(a, -1)
    search(a, 18)

输出：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
[0, 2, 4, 6]
===================================
x = 0
left:0, mid:1, right:3
left:0, mid:0, right:0
循环结束，left:0, mid:0, right:-1
===================================
x = 2
left:0, mid:1, right:3
left:0, mid:0, right:0
循环结束，left:1, mid:0, right:0
===================================
x = 4
left:0, mid:1, right:3
left:2, mid:2, right:3
循环结束，left:2, mid:2, right:1
===================================
x = 6
left:0, mid:1, right:3
left:2, mid:2, right:3
left:3, mid:3, right:3
循环结束，left:3, mid:3, right:2
===================================
x = 1
left:0, mid:1, right:3
left:0, mid:0, right:0
循环结束，left:1, mid:0, right:0
===================================
x = 5
left:0, mid:1, right:3
left:2, mid:2, right:3
left:3, mid:3, right:3
循环结束，left:3, mid:3, right:2
===================================
x = -1
left:0, mid:1, right:3
left:0, mid:0, right:0
循环结束，left:0, mid:0, right:-1
===================================
x = 18
left:0, mid:1, right:3
left:2, mid:2, right:3
left:3, mid:3, right:3
循环结束，left:4, mid:3, right:3

这个好像所有的都是left指向答案。

但如果改成

1
2
3
4
if arr[mid] <= x:
    left = mid + 1
elif arr[mid] > x:
    right = mid - 1

输出：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
[0, 2, 4, 6]
===================================
x = 0
left:0, mid:1, right:3
left:0, mid:0, right:0
循环结束，left:1, mid:0, right:0
===================================
x = 2
left:0, mid:1, right:3
left:2, mid:2, right:3
循环结束，left:2, mid:2, right:1
===================================
x = 4
left:0, mid:1, right:3
left:2, mid:2, right:3
left:3, mid:3, right:3
循环结束，left:3, mid:3, right:2
===================================
x = 6
left:0, mid:1, right:3
left:2, mid:2, right:3
left:3, mid:3, right:3
循环结束，left:4, mid:3, right:3
===================================
x = 1
left:0, mid:1, right:3
left:0, mid:0, right:0
循环结束，left:1, mid:0, right:0
===================================
x = 5
left:0, mid:1, right:3
left:2, mid:2, right:3
left:3, mid:3, right:3
循环结束，left:3, mid:3, right:2
===================================
x = -1
left:0, mid:1, right:3
left:0, mid:0, right:0
循环结束，left:0, mid:0, right:-1
===================================
x = 18
left:0, mid:1, right:3
left:2, mid:2, right:3
left:3, mid:3, right:3
循环结束，left:4, mid:3, right:3

这就像是如果在，是right指向，如果不在，是left指向。

。。。

。。。

我知道了！我要得有个问题先！

问题：找到第一个大于等于x的位置

思考的步骤应该是这样的：

  1. 闭区间[left,right]，这是每一次查询的区间，循环退出的条件是区间为空，也就是left在right的右边；
  2. 找到mid，与要寻找的x进行比较，将区间分成两部分，一部分符合条件（大于等于x），另一部分是不符合条件的（小于x）
  3. 根据比较的结果，调整left或者right
  4. 因为mid在比较了之后，就可以将它划分到其中的一个部分，又因为是闭区间，所以调整后的区间就不包括mid
  5. 根据这道题的要求，就有了一个非常重要的事情：left左边的一定都比x小，right右边的一定都大于等于x，这两个点不确定
  6. 最后一定是left == right
    1. arr[mid] >= x，调整right后退出循环，left是结果，因为right右边的一定都大于等于x，而整个区间已经全部划分完了，题目要求的第一个大于等于x的位置就是right + 1，也就是left;
    2. arr[mid] < x，调整left后退出循环，left是结果，原因和上面差不多。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def search(arr, x):
    print("===================================")
    print(arr)
    print("x =", x)
    left = 0
    right = len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        print(f"left:{left}, mid:{mid}, right:{right}")
        if arr[mid] >= x:
            right = mid - 1
        elif arr[mid] < x:
            left = mid + 1
        # else:
        #     break
    print(f"循环结束，left:{left}, mid:{mid}, right:{right}")
    return left

同样的思考过程可以写出：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
# 二分查找
# >=x
# 第一个大于等于 x 的位置
# x 的第一个位置
def lower_bound(arr, x):
    left = 0
    right = len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        # print(f"left:{left}, mid:{mid}, right:{right}")
        if arr[mid] >= x:
            right = mid - 1
        elif arr[mid] < x:
            left = mid + 1
    # print(f"循环结束，left:{left}, mid:{mid}, right:{right}")
    return left


# <=x
# x 的最后一个位置
def upper_bound(arr, x):
    left = 0
    right = len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        # print(f"left:{left}, mid:{mid}, right:{right}")
        if arr[mid] <= x:
            left = mid + 1
        else:
            right = mid - 1
    # print(f"循环结束，left:{left}, mid:{mid}, right:{right}")
    return right


# 第一个小于 x 的位置
# x 的前一个位置
def lower_bound2(arr, x):
    left = 0
    right = len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        # print(f"left:{left}, mid:{mid}, right:{right}")
        if arr[mid] < x:
            left = mid + 1
        else:
            right = mid - 1
    # print(f"循环结束，left:{left}, mid:{mid}, right:{right}")
    return right


# >x
# 第一个大于 x 的位置，x 的后一个位置
def upper_bound2(arr, x):
    left = 0
    right = len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        # print(f"left:{left}, mid:{mid}, right:{right}")
        if arr[mid] > x:
            right = mid - 1
        else:
            left = mid + 1
    # print(f"循环结束，left:{left}, mid:{mid}, right:{right}")
    return left

开区间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
# 开区间
# >=x
# 第一个大于等于 x 的位置
# x 的第一个位置
def lower_bound(arr, x):
    # 开区间
    left = -1
    right = len(arr)
    while left +1< right:  # 这时候，区间就空了，比如（2，3）
        mid = (left + right) // 2
        # print(f"left:{left}, mid:{mid}, right:{right}")
        if arr[mid] >= x:
            right = mid
        elif arr[mid] < x:
            left = mid
    # print(f"循环结束，left:{left}, mid:{mid}, right:{right}")
    return right


# <=x
# x 的最后一个位置
def upper_bound(arr, x):
    left = -1
    right = len(arr)
    while left +1< right:
        mid = (left + right) // 2
        # print(f"left:{left}, mid:{mid}, right:{right}")
        if arr[mid] <= x:
            left = mid
        else:
            right = mid
    # print(f"循环结束，left:{left}, mid:{mid}, right:{right}")
    return left


# <x
# 第一个小于 x 的位置
# x 的前一个位置
def lower_bound2(arr, x):
    left = -1
    right = len(arr)
    while left +1< right:
        mid = (left + right) // 2
        # print(f"left:{left}, mid:{mid}, right:{right}")
        if arr[mid] < x:
            left = mid
        else:
            right = mid
    # print(f"循环结束，left:{left}, mid:{mid}, right:{right}")
    return left


# >x
# 第一个大于 x 的位置，x 的后一个位置
def upper_bound2(arr, x):
    left = -1
    right = len(arr)
    while left +1< right:
        mid = (left + right) // 2
        # print(f"left:{left}, mid:{mid}, right:{right}")
        if arr[mid] > x:
            right = mid
        else:
            left = mid
    # print(f"循环结束，left:{left}, mid:{mid}, right:{right}")
    return right


if __name__ == '__main__':
    a = [0, 2, 3, 3, 3, 3, 4, 6]
    x_list = a + [-1, 1, 5, 10]
    for i in x_list:
        print("===================================")
        print(a)
        print("x =", i)
        print(">=x，第一个大于等于 x 的位置")
        # >=x，第一个大于等于 x 的位置
        # x 的第一个位置
        print(lower_bound(a, i))

        print("<=x x的最后一个位置")
        # <=x x的最后一个位置
        print(upper_bound(a, i))
        # 可以转换为求 x+1 的第一个位置 -1
        print(lower_bound(a, i + 1) - 1)

        print("<x 第一个小于 x 的位置，x 的前一个位置")
        # <x 第一个小于 x 的位置，x 的前一个位置
        print(lower_bound2(a, i))
        # 可以传唤为 x-1 的最后一个位置
        # 最后一个位置转换成 x+1 的第一个位置 -1
        # 所以最后转换成 x 的第一个位置 -1
        print(lower_bound(a, i) - 1)

        print(">x，第一个大于 x 的位置，x 的后一个位置")
        # >x，第一个大于 x 的位置，x 的后一个位置
        print(upper_bound2(a, i))
        # 可以转换为求 x+1 的第一个位置
        print(lower_bound(a, i + 1))


发现，在开区间里，符合条件的时候调整谁最后就返回谁，闭区间就相反。

左闭右开

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
# >=x
# 第一个大于等于 x 的位置
# x 的第一个位置
def lower_bound(arr, x):
    left = 0
    right = len(arr)
    while left < right:  # 等于了区间就空了，比如[2，2）
        mid = (left + right) // 2
        # print(f"left:{left}, mid:{mid}, right:{right}")
        if arr[mid] >= x:
            right = mid
        elif arr[mid] < x:
            left = mid + 1
    # print(f"循环结束，left:{left}, mid:{mid}, right:{right}")
    return right


# <=x
# x 的最后一个位置
def upper_bound(arr, x):
    left = 0
    right = len(arr)
    while left < right:
        mid = (left + right) // 2
        # print(f"left:{left}, mid:{mid}, right:{right}")
        if arr[mid] <= x:
            left = mid + 1
        else:
            right = mid
    # print(f"循环结束，left:{left}, mid:{mid}, right:{right}")
    return left - 1  # right - 1


# <x
# 第一个小于 x 的位置
# x 的前一个位置
def lower_bound2(arr, x):
    left = 0
    right = len(arr)
    while left < right:
        mid = (left + right) // 2
        # print(f"left:{left}, mid:{mid}, right:{right}")
        if arr[mid] < x:
            left = mid + 1
        else:
            right = mid
    # print(f"循环结束，left:{left}, mid:{mid}, right:{right}")
    return left - 1  # right - 1


# >x
# 第一个大于 x 的位置，x 的后一个位置
def upper_bound2(arr, x):
    left = 0
    right = len(arr)
    while left < right:
        mid = (left + right) // 2
        # print(f"left:{left}, mid:{mid}, right:{right}")
        if arr[mid] > x:
            right = mid
        else:
            left = mid + 1
    # print(f"循环结束，left:{left}, mid:{mid}, right:{right}")
    return left   # right

考虑输出什么的时候，就想

  1. left（或者right)本身因为开或闭是否要算，闭不算开要算
  2. 然后看它或者它那一边是符合条件的就输出。

关于(left + right + 1) // 2

我觉得这不重要，重要的是根据上面的步骤考虑清楚区间的范围以及left和right指向的情况就行，保证mid在区间里就行。

奥，因为向上取整，所以左闭右开不能这么做。怪不得向下取整的时候没有左开右闭呢。