二分查找

   数据结构与算法 / 查找算法 14 分钟读完 (大约2042个字)3次访问

二分查找

一、代码模板

常见的二分查找模板代码如下：

1
2
3
4
5
6
7
8
9
10
left = low, right = high;
while (left <= right) {
    int mid = left + (right - left) / 2;
    if (满足条件) {
        right = mid - 1;
    } else {
        left = mid + 1;
    }
}
return left; // 或 right

在二分查找中，有几个需要注意的地方：

  • 循环条件（while (left <= right)）
  • 中值计算（mid）
  • 区间收缩（left = mid + 1、right = mid - 1）
  • 返回值（left、right）

这些地方写错了就很容易导致最后的结果不对。

二、循环条件

在二分查找中，常用的循环条件有 2 种：

  • while (left <= right)
  • while (left < right)

什么时候用 <=？什么时候用 < 呢？实际上这和区间定义有关。

常见的区间定义可以分为 2 种：

  • 左闭右闭 [low, high]
  • 左闭右开 [low, high)

不同的区间定义，循环条件的写法也不一样。为什么呢？这是因为，

  • 区间定义属于是循环不变量，在整个循环过程中要一直保持有意义

所以循环条件的写法，其实是根据区间是否有意义来决定的：

  • 左闭右闭：当 left==right 时，[left, right] 有意义，因此有 = 号
  • 左闭右开：当 left==right 时，[left, right) 无意义，因此无 = 号

因此，循环条件上要不要 = 号，取决于区间定义是否有意义。

  • 左闭右闭 [low, high]：while (left <= right)
  • 左闭右开 [low, high)：while (left < right)

正常来说，这两种写法都是可行的，不过还是，

  • 推荐使用左闭右闭 [low, high]：while (left <= right)

因为两边都是闭区间，是对称的，所以两边的区间操作也是对称的，不容易出错。

三、中值计算

一般来说，二分中值的计算方式有以下几种：

  1. mid = (left + right) / 2
  2. mid = left + (right - left) / 2
  3. mid = left + ((right - left) >> 1)

使用哪种方式比较好呢？

  • 推荐使用第 2 种：mid = left + (right - left) / 2

第 1 种存在整数溢出问题，所以用的比较少。

第 3 种和第 2 种本质上是一样的，而且从理论上说移位 >> 比除法 / 还要快。

但是 >> 的优先级比 + 号低，需要加多一层括号，而括号很容易遗漏，不够直观。

所以从整体上来说，还是第 2 种写法更好一点。

四、区间收缩

二分查找实际上就是收缩左右边界，直到找到满足条件的值为止。

不过区间收缩的方式有好几种，包括：

  • left = mid + 1
  • right = mid - 1
  • left = mid
  • right = mid

这几种方式可以组合成各种情况，用不好的话，就很容易造成死循环。

比如说，使用 left = mid 和 right = mid - 1 来这样组合：

1
2
3
4
5
6
7
8
while (left <= right) {
    int mid = left + (right - left) / 2;
    if (arr[mid] >= x) {
        left = mid;
    } else {
        right = mid - 1;
    }
}

假设此时 left = 0, right = 1, arr = {1, 2}, x = 1，那么代码就会陷入死循环。

死循环的原因就是左右边界没有收缩，导致一直无法达到循环结束条件。

  • 死循环基本都是出现在 left = mid 或 right = mid 上

因为 left = mid 和 right = mid 在某些情况下可能会导致区间一直没有收缩。

区间收缩的正确使用方式应该是怎么样呢？这就要看区间定义了：

  • 左闭右闭 [low, high]：left = mid + 1 和 right = mid - 1
  • 左闭右开 [low, high)：left = mid + 1 和 right = mid
  • 左开右闭 (low, high]：left = mid 和 right = mid - 1
  • 左开右开 (low, high)：left = mid 和 right = mid

比如说，要寻找第一个 >= x 的位置，不同区间的写法如下：

1）左闭右闭 [low, high]

1
2
3
4
5
6
7
8
9
10
11
while (left <= right) {
    // left <= mid <= right
    int mid = left + (right - left) / 2;
    if (arr[mid] >= x) {
        // [left, mid - 1]，因为 mid <= right，所以区间在收缩
        right = mid - 1;
    } else {
        // [mid + 1, right]，因为 mid >= left，所以区间在收缩
        left = mid + 1;
    }
}

2）左闭右开 [low, high)

1
2
3
4
5
6
7
8
9
10
11
while (left < right) {
    // left <= mid < right
    int mid = left + (right - left) / 2;
    if (arr[mid] >= x) {
        // [left, mid)，因为 mid < right，所以区间在收缩
        right = mid;
    } else {
        // [mid + 1, right)，因为 mid >= left，所以区间在收缩
        left = mid + 1;
    }
}

区间的收缩方式要和区间定义相匹配，才能保证区间收缩的正确性。

而循环内区间收缩的核心思想就是：

  • 不管哪种区间定义，都要保证每轮循环结束后，区间在缩小

只要保证区间一直在缩小，那么就不会出现死循环的问题。

五、返回值

在一般的二分查找中，返回值有时候是 left，有时候是 right。

比如说，要寻找第一个 >= x 的位置，返回值就是 left：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int firstGreatEqualSearch(int[] arr, int x) {
    int n = arr.length;
    // 循环不变量（循环中始终成立的条件）：
    // arr[left - 1] < x
    // arr[right + 1] >= x
    int left = 0, right = n - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] >= x) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    // 循环终止条件：right + 1 == left
    return left; // 或 right + 1
}

要寻找最后一个 <= x 的位置，返回值就是 right：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int lastLessEqualSearch(int[] arr, int x) {
    int n = arr.length;
    // 循环不变量（循环中始终成立的条件）：
    // arr[left - 1] <= x
    // arr[right + 1] > x
    int left = 0, right = n - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] <= x) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    // 循环终止条件：right + 1 == left
    return right; // 或 left - 1
}

按照这种模板写代码的话，就需要，

  • 末尾返回值根据循环不变量来决定是 left 还是 right

但是，这种末尾返回值的写法，需要根据实际情况来调整，不好理解，写起来也容易出错。

因此，可以换另外一种写法：

  • 将末尾返回值，改成在循环体内判断成立条件，然后返回值

比如，要寻找第一个 >= x 的位置：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int firstGreatEqualSearch(int[] arr, int x) {
    int n = arr.length;
    int left = 0, right = n - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] >= x) {
            // 改成在循环体内判断成立条件，然后返回值
            if (mid == 0 || arr[mid - 1] < x) {
              return mid;
            }
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    // 注意，当所有元素都不满足时，这里返回了 -1
    // 而上面的代码则返回的不一样，上面返回的是 n
    return -1;
}

这种循环体内返回的写法虽然没那么简洁，但是至少它逻辑清晰、简单易懂。

因此，除非对末尾返回值的写法很熟练了，否则推荐用在循环中返回值的写法。

总结

区间定义 左闭右闭 [low, high] 左闭右开 [low, high)
初始边界 low = 0, high = n - 1 low = 0, high = n
循环条件 left <= right left < right
中值计算 mid = left + (right - left) / 2 mid = left + (right - left) / 2
收缩方式 left = mid + 1, right = mid - 1 left = mid + 1, right = mid
终止情况 left == right + 1 left == right
left 范围 [low, high + 1] [low, high]
right 范围 [low - 1, high] [low, high]

参考

https://www.hello-algo.com/chapter_searching/binary_search/

https://www.programmercarl.com/0704.%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE.html

https://time.geekbang.org/column/article/42733

附录

等于给定值的位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int equalSearch(int[] arr, int x) {
    int n = arr.length;
    int low = 0, high = n - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == x) {
            return mid;
        } else if (arr[mid] < x) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return -1;
}

第一个等于给定值的位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int firstEqualSearch(int[] arr, int x) {
    int n = arr.length;
    int left = 0, right = n - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == x) {
            if (mid == 0 || arr[mid - 1] != x) {
              return mid;
            }
            right = mid - 1;
        } else if (arr[mid] < x) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
}

最后一个等于给定值的位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int lastEqualSearch(int[] arr, int x) {
    int n = arr.length;
    int left = 0, right = n - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == x) {
            if (mid == n - 1 || arr[mid + 1] != x) {
              return mid;
            }
            left = mid + 1;
        } else if (arr[mid] < x) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
}

第一个大于等于给定值的位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int firstGreatEqualSearch(int[] arr, int x) {
    int n = arr.length;
    int left = 0, right = n - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] >= x) {
            if (mid == 0 || arr[mid - 1] < x) {
              return mid;
            }
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return -1;
}

最后一个小于等于给定值的位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int lastLessEqualSearch(int[] arr, int x) {
    int n = arr.length;
    int left = 0, right = n - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] <= x) {
            if (mid == n - 1 || arr[mid + 1] > x) {
              return mid;
            }
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
}

二分查找

http://example.com/algorithm/binary/binary_search/

作者

jiaduo

发布于

2022-09-08

更新于

2023-10-07

许可协议

 
×
文章
斜堆 斜堆一、什么是斜堆？斜堆（Skew Heap），也称斜树（Skew Tree），自适应堆(Self-Adjusting Heap)，是一种自平衡二叉堆数据结构。 斜堆是左倾堆（Leftist Heap 左倾堆 左倾堆一、什么是左倾堆？左倾堆（Leftist Heap），也称为左偏树（Leftist Tree）、左偏堆，最左堆等。 和二叉堆（即常见的堆，基于数组实现的完全堆）一样，左倾堆也是优先队列的一种实现 KMP 算法 KMP 算法KMP 算法是一种字符串匹配算法，可以在 O(n+m) 的时间复杂度内实现两个字符串的匹配。 KMP 算法是根据三位作者（D.E.Knuth，J.H.Morris 和 V.R.Pratt） BF 算法 BF 算法BF 算法，即 Brute Force，暴力匹配算法，也叫朴素匹配算法。 一、原理所谓的暴力匹配，就是： 检查主串的所有子串，看是否与模式串匹配 比如，主串是 ababababca，模式串是 堆排序 堆排序一、什么是堆排序？ 基于堆实现的排序算法 利用堆顶的有序性（最大值或最小值）来实现对数组的排序 二、为什么要用堆排序？ 唯一能够同时最优地利用空间和时间的排序算法 缺点是很少和相邻元素比较，导致
页面
资源 分类 关于 标签
分类
方法论 (方法论) 设计模式 (方法论/设计模式) 生活感想 (生活感想) 面向对象 (方法论/面向对象) 代码规范 (方法论/代码规范)
标签
设计模式 (设计模式) 生活 (生活) 其他 (其他) 代码规范 (代码规范) 《代码整洁之道》 (《代码整洁之道》)