lurenaa的博客

🐶结构1辨析

  这里介绍第一种结构

1
2
3
4
5
6
7
8
9
10
11
12
function binary_search(A, n, T) is
    L := 0
    R := n − 1
    while L ≤ R do
        m := floor((L + R) / 2)
        if A[m] < T then
            L := m + 1
        else if A[m] > T then
            R := m - 1
        else:
            return m
    return unsuccessful

  这里m := floor((L + R) / 2)有时会替换成m := ceiling((L + R) / 2)，简单来说就是(L + R) / 2替换成(L + R + 1) / 2。

  在以上结构中这个语句的替换不会影响算法的正确性。不过在目标T在数组A中有多个的时候，可能会影响到底返回多个T中的哪一个。

  比如[1 2 2 2 3 4]，在floor时返回的下标是2，在ceiling时返回的下标是3.

🦊优化1

  这里有一个可以小优化的地方，L+R存在整形溢出的情况，可以改为L + （R - L) / 2避免溢出问题。

🐹结构2辨析

  这其实也是一种优化，因为以上结构中在每个循环中比较次数太多，可以使用以下结构来代替。

1
2
3
4
5
6
7
8
9
10
11
12
function binary_search_alternative(A, n, T) is
    L := 0
    R := n − 1
    while L != R do
        m := ceil((L + R) / 2)
        if A[m] > T then
            R := m - 1
        else:
            L := m
    if A[L] = T then
        return L
    return unsuccessful

或者

1
2
3
4
5
6
7
8
9
10
11
12
function binary_search_alternative(A, n, T) is
    L := 0
    R := n − 1
    while L != R do
        m := floor((L + R) / 2)
        if A[m] < T then
            L := m + 1
        else:
            R := m
    if A[L] = T then
        return L
    return unsuccessful

  以上两种结构可以在每次循环中减少一次的比较。

  并且值的注意的是以下两种结构是错误的：

1
2
3
4
5
6
7
8
9
10
11
12
👿function binary_search_alternative(A, n, T) is
    L := 0
    R := n − 1
    while L != R do
        m := ceil((L + R) / 2)
        if A[m] < T then
            L := m + 1
        else:
            R := m
    if A[L] = T then
        return L
    return unsuccessful

假设在[2 3 4]中查找2，

第一趟： L = 0 R = 5 m = 1 A[m] > T

第二趟: L = 0 R = 1 m = 1 A[m] > T

第三趟：L = 0 R = 1 m = 1 A[m] > T

…

第N趟：L = 0 R = 1 m = 1 A[m] > T

这里会导致无线循环，因为ceiling取上限，并且我们将m取在右边，导致区间在左边没法收敛。

同理，下面结构也是错误的：

1
2
3
4
5
6
7
8
9
10
11
12
👿function binary_search_alternative(A, n, T) is
    L := 0
    R := n − 1
    while L != R do
        m := floor((L + R) / 2)
        if A[m] > T then
            R := m - 1
        else:
            L := m
    if A[L] = T then
        return L
    return unsuccessful

可以[2 3 4]中查找4来试试。

🙈结构3辨析

  在存在重复元素的时候，究竟该返回哪一个呢？比如[1,2,4,4,4,5,6,7]查找4，是返回2还是3，或者4？

  下面这样一个结构可以返回最左边的元素：

1
2
3
4
5
6
7
8
9
10
function binary_search_leftmost(A, n, T):
    L := 0
    R := n
    while L < R:
        m := floor((L + R) / 2)
        if A[m] < T:
            L := m + 1
        else:
            R := m
    return L

在找到元素后，依旧会通过R = m向左边收缩。

  下面这样一个结构可以返回最右边的元素：

1
2
3
4
5
6
7
8
9
10
function binary_search_rightmost(A, n, T):
    L := 0
    R := n
    while L < R:
        m := floor((L + R) / 2)
        if A[m] <= T:
            L := m + 1
        else:
            R := m
    return R - 1

在找到元素后，依旧会通过left = m + 1向右边收缩。


 上一页

算法