新人须知
新人须知

二分算法

大家应该玩过一个两人猜数字的游戏吧，让对方在心里想一个数字，你来猜，每当你猜一次，他会告诉你猜大了还是猜小了，你根据对方的回答来继续往下猜，直到猜中为止，两人交换来玩，看谁猜中所用的次数更少。

为了更快猜到答案，有一个技巧，那就是每次都猜可能的数字范围的中间值，这样下来，每次都会直接去除掉一半的可能性，平均下来，这样猜中所用的次数都会更少。

实际上，这种技巧就是我们今天要谈到的二分查找（Binary Search），每次砍掉一半，让得出答案的效率更高。

哈佛有一门非常受欢迎的计算机科学导论课 CS50，该课的老师 David Malan 经常在课堂上通过手撕一本很厚的电话薄来展示二分法的思想，非常有感染力，感兴趣的可以去看看。CS50 B站视频

二分查找

二分查找是一种用于在有序数组中查找特定元素的高效算法。它的核心思想是在每一轮查找中将中间元素与目标元素进行比较，比较后将搜索的范围减半，从而快速定位到目标元素的位置。

在二分查找算法中，数组中的元素必须是有序的，这意味着它们必须按照升序或降序排列。但是，有序数组中可以有重复的元素。

二分查找算法的步骤如下：

  1. 确定要搜索范围的起点与终点。对于数组来说，也就是数组的起始索引和结束索引。
  2. 计算出中间元素的位置。
  3. 将中间元素与目标元素进行比较，有下面几种情况
    • 如果中间元素等于目标元素，则找到了目标元素，返回其索引。
    • 如果中间元素大于目标元素，则目标元素应该在左半部分，可以将右半部分舍弃掉，搜索范围缩小一半。
    • 如果中间元素小于目标元素，则目标元素应该在右半部分，可以将左半部分舍弃掉，搜索范围缩小一半。
  4. 重复步骤 2 和 3，不断缩小搜索范围，直到找到目标元素或搜索范围为空。

下面通过一个简单的例子来演示一下二分查找算法。

假设我们有如下一个由小到大排序好的数组，包含 10 个元素，请问数字 30 所在的索引是多少呢？

int q[] = {1, 2, 7, 10, 18, 21, 30, 32, 40, 43};

如果我们人眼一看就知道了，数字 30 所在位置的索引是 6，但对于程序来说，必须通过算法去真正找到才能知道，当然，如果给你一万，或十万条数据，要快速找到一个数字所在的位置，对人来说就很困难了，但对于程序来说，也是瞬间的事情。

我们可以根据上面的算法步骤写一个简单的二分查找函数：

int binary_search(int q[], int l, int r, int target) {
  while (l <= r) {
    int mid = (l + r) / 2; // 计算中间元素的索引
    
    // 比较中间元素与目标元素，修正索引起点或终点（缩小搜索范围）
    if (q[mid] > target) r = mid - 1;
    else if (q[mid] < target) l = mid + 1;
    else return mid;
  }
  return -1; // 如果元素不存在，则返回 -1
}

需要注意的是：

  • 二分查找要求数组是有序的。如果数组未排序，你需要先对其进行排序。
  • 当数组中存在重复元素时，二分查找会找到第一个等于目标值的元素。

示例：二分查找元素

题目描述

请在一个有序递增数组中（不存在相同元素），采用二分查找，找出值 xx 的位置，如果 xx 在数组中不存在，请输出 -1 ！

输入描述

第一行，两个整数 n，xn，x ，nn 代表数组元素个数（n≤106n \le 10^6），xx 代表要查找的数（0≤x≤1080 \le x \le 10^8）

第二行，nn 个数，代表数组的 nn 个递增元素（1≤数组元素值≤1081 \le 数组元素值 \le 10^8）

输出描述

xx 在数组中的索引位置，或者 -1。

输入输出样例

输入数据

10 30 1 2 7 10 18 21 30 32 40 43

输出数据

6

实现代码

#include <iostream>
using namespace std;

const int N = 1e6 + 10;
int q[N];

int binary_search(int q[], int l, int r, int target) {
  while (l <= r) {
    int mid = (l + r) / 2; 
    
    if (q[mid] > target) r = mid - 1;
    else if (q[mid] < target) l = mid + 1;
    else return mid;
  }
  return -1;
}


int main() {
    int n, x;
    cin >> n >> x;
    
    for (int i = 0; i < n; i++) cin >> q[i];
    
    cout << binary_search(q, 0, n - 1, x) << endl;
    
    return 0;
}

代码解析

下面我们通过图中来看看算法的整个执行过程。

第 1 步，确定初始的搜索范围

l 和 r 代表搜索范围的起始与结束索引，初始值就应该是该数组的第一个元素（索引为 00）和最后一个元素的索引值（索引为 n−1n-1）。

第 2 步，确定中间元素

这时根据公式 mid = (l + r) / 2 计算出中间元素的索引值 4，目前数组元素及对应几个变量值如下图所示：

第 3 步，比较中间元素与目标元素

这时中间元素 q[mid] 为 18，目标元素是 30，中间元素是小于目标元素的，目标元素应该在数组的右半部分，因此可以将左半部分舍弃掉，重新修正左侧的索引值 l，搜索范围缩小一半。如下图所示。

第 4 步，重新比较并修正搜索范围

新的中间元素为 32，是大于目标元素的，目标元素应该在数组的左半部分，因此可以将右半部分舍弃掉，重新修正右侧的索引值 r，搜索范围再缩小一半。如下图所示。

第 5 步，再次比较并修正搜索范围

新的中间元素为 21，是小于目标元素的，目标元素应该在数组的右半部分，因此可以将左半部分舍弃掉，重新修正左侧的索引值 l，搜索范围再缩小一半，这时可以发现 l、r 与 mid 指向同一个值，且为目标元素，得出最终结果。如下图所示。

二分查找算法模板

算法模板，也可以理解成一种经过大量实践总结出来的「套路」，在理解的基础上记下这些套路是很有必要的。

  • 可以帮助我们更好的理解算法（为什么模板要这么写）
  • 本身这些模板也考虑到了各种边界问题，一般不太会出错
  • 如果在竞赛或实践中，直接使用模板可以提升效率，节约时间

在上面的示例中，我们假定数组元素是不重复的，如果存在重复元素，二分的场景就会复杂一些，会讨论到各种情况，主要是处理各种边界问题。

其实二分的算法思想本身还是比较好理解的，就是因为要处理各种边界问题，细节上很容易考虑不周。

例如，对于下面的从小到大排序后的数组，有重复元素

{1, 2, 7, 10, 10, 10, 30, 30, 40, 43}

下面这一些问题，如何解决？

  • 数字 8 是否在数组当中
  • 数字 10 出现的第一个位置是多少（左边界）
  • 数字 10 出现的最后一个位置是多少（右边界）
  • 第一个大于 25 的数字是多少（左边界）
  • 数字 30 连续有多个，它的起始位置是多少（边界范围）

在代码实现中，稍微不注意就会出错，给大家介绍两个二分查找的通用模板，在理解的基础上，熟练掌握这两个模板（记下来），基本上所有的整数二分问题就没多大问题了。

二分查找模板 1

// 区间被划分为 [l, mid] 和 [mid + 1, r] 时使用
int binary_search(int l, int r) {
  while (l < r) {
    // int mid = l + (r - l) >> 1;
    int mid = (l + r) / 2;
    if (比较中间元素与目标元素) r = mid;
    else l = mid + 1;
  }
  return l; // 根据实际需求对这里返回的值需要做处理
}

二分查找模板 2

// 区间被划分为 [l, mid - 1] 和[mid, r] 时使用
int binary_search_2(int l, int r) {
  while (l < r) {
    // int mid = 1 + l + (r - l) >> 1;
    int mid = 1 + (l + r) / 2;
    if (比较中间元素与目标元素) l = mid;
    else r = mid - 1;
  }
  return l; // 根据实际需求对这里返回的值需要做处理
}

我们下面会通过几个不同的练习来帮助理解和使用上面这两个模板，在练习之前，有几点需要说明一下。

  1. 如何取到中间元素值

常用的方法是 int mid = (l + r) / 2 ，但有一个问题，如果 l 与 r 特别大时，l + r 的和很有可能就会爆掉（超过数的最大表示范围）。因此我们做了一个数学上的等价变换 l + (r - l) / 2 ，变换后，由于没有了两个大数的直接加法，很大程度上就避免了爆掉的问题。

另外，我们也可以看到用右移位运算 >> 来替代除以 2 的运算。

  1. 模板 2 中的 mid 加 1 处理

在模板 2 中，我们在取中间值时多加了个 1，为什么要多加 1 呢？

这是因为在 C++ 中，我们整数相除的结果都是向下取整，多加 1 是为了避免出现死循环的问题。

想像一下，假设数组只有两个元素，l 的值为 0，r 的值为 1，向下取整计算 (l + r) / 2 ，得到 mid 的值为 0，如果这时条件判断进到 l = mid，可以发现左边界实际没变化（l 仍然是 0， r 仍然是 1），这样就形成了一个死循环。

  1. 比较中间元素与目标元素

在实际解决问题时，如何比较中间元素与目标元素，是根据题目要求来的，如果条件满足需要舍弃到左半部分，就选模板2，否则选择模板1 。

  1. 最后函数的返回值

通常来说，我们在实际使用模板时，只需要动两部分内容：一部分是「比较中间元素与目标元素」，另一部分就是函数的返回值。这都是根据题目的具体需求来调整的，在接下来的练习中会看到如可来调整。

理解模板最好的办法就是去用，用这两个模板去解决不同的问题。下面我们就用模板来完成前面的示例：二分查找元素。

由于题目中已知是有序数组（且数组中无重复元素），用模板1和模板2都可以，我们可以两个都试试。

示例：二分查找元素（使用模板1）

#include <iostream>
using namespace std;

const int N = 1e6 + 10;
int q[N], n, x;

// 使用模板1
int binary_search(int l, int r) {
  while (l < r) {
    int mid = (l + r) / 2;
    if (q[mid] >= x) r = mid;
    else l = mid + 1;
  }
  if (q[l] != x) return -1; // 查找元素不存在
  else return l; 
}

int main() {
    cin >> n >> x;
    
    for (int i = 0; i < n; i++) cin >> q[i];
    
    cout << binary_search(0, n - 1) << endl;
    
    return 0;
}

示例：二分查找元素（使用模板2）

#include <iostream>
using namespace std;

const int N = 1e6 + 10;
int q[N], n, x;

// 使用模板2
int binary_search(int l, int r) {
  while (l < r) {
    int mid = 1 + (l + r) / 2;
    if (q[mid] <= x) l = mid;
    else r = mid - 1;
  }
  if (q[l] != x) return -1; // 查找元素不存在
  else return l; 
}

int main() {
    cin >> n >> x;
    
    for (int i = 0; i < n; i++) cin >> q[i];
    
    cout << binary_search(0, n - 1) << endl;
    
    return 0;
}

可以看到，对于这个例子来说，因为数组没有重复元素，使用模板1或模板2均可完成，变动的只有两个地方：

  • 中间元素与目标元素的比较部分，这决定了是使用模板1还是模板2
  • 另一个是返回值，这里因为要处理元素不存在的情况，因此我们在返回前做了一次判断。

上面的二分查找模板基本上可以应对所有与整数二分相关的问题，下面再通过一些二分查找相关的练习来熟悉一下。

练习：二分查找左边界

题目描述

请在一个有序不递减的数组中（数组中有相等的值），采用二分查找，找到值 xx 第 1 次出现的位置，如果不存在 xx 请输出 −1。

请注意：本题要求出 qq 个 xx ，每个 xx 在数组中第一次出现的位置。

比如有 6 个数，分别是：1 2 2 2 3 3，那么如果要求 3 个数：3 2 5，在数组中第一次出现的位置，答案是：4 1 −1。

输入

第一行，一个整数 nn，代表数组元素个数（n≤105n \le 10^5）

第二行，nn 个整数，用空格隔开，代表数组的 nn 个元素（1≤数组元素的值<1081 \le 数组元素的值\lt 10^8）

第三行，一个整数 qq，代表有要求出 qq 个数首次出现的位置（q≤105q \le 10^5)

第四行，qq 个整数，用空格隔开，代表要找的数（1≤要找的数≤1051 \le 要找的数 \le 10^5）

输出

输出 1 行，含 qq 个整数，按题意输出要找的每个数在数组中首次出现的索引位置，如果不存在这样的数，请输出 −1。

输入输出样例

输入数据

6 1 2 2 2 3 3 3 3 2 5

输出数据

4 1 -1

题目解析

确定要选用的模板，因为这个任务是找数字在数组中首次出现的位置，也就是找 **≥要找的数字\ge 要找的数字**的第 1 个元素。

我们的判断条件就是：中间元素 ≥ 目标元素，则目标元素应该在左半部分，可以将右半部分舍弃掉，修正右边界 ，r = mid ，因此选择模板 1 。

另外，由于可能要找的元素不存在，因此在二分查找完，函数返回时，我们来处理元素不存的情况，在查找停止时，l 所在的位置元素如果不等于要查找的元素，就表示没有找到，就应该返回 -1 。

还有一点需要注意，由于要读入的数据比较多，我们就用 scanf() 和 printf() 来读入和输出，这样效率会更高一些。

实现代码

// 二分查找左边界
#include <iostream>
using namespace std;

const int N = 1e6 + 10;
int q[N], n, k;

// 根据分析选择模板 1
int binary_search(int l, int r, int x) {
  while (l < r) {
    int mid = (l + r) / 2;
    if (q[mid] >= x) r = mid;
    else l = mid + 1;
  }
  
  if (q[l] != x) return -1;
  else return l;
}

int main() {
    scanf("%d", &n);
    
    for (int i = 0; i < n; i++) scanf("%d", &q[i]);
    
    cin >> k;
    
    while (k--) {
      int x;
      scanf("%d", &x);
      
      int l = 0, r = n - 1;
      
      cout << binary_search(l, r, x) << " ";
    }

    return 0;
}

练习：二分查找右边界

题目描述

请在一个有序不递减的数组中（数组中有相等的值），采用二分查找，找到值 xx 最后 1 次出现的位置，如果不存在 xx 请输出 −1。

请注意：本题要求出 qq 个 xx ，每个 xx 在数组中最后一次出现的位置。

比如有 6 个数，分别是：1 2 2 2 3 3，那么如果要求 3 个数：3 2 5，在数组中最后一次出现的位置，答案是：5 3 −1。

输入

第一行，一个整数 nn，代表数组元素个数（n≤105n \le 10^5）

第二行，nn 个整数，用空格隔开，代表数组的 nn 个元素（1≤数组元素的值<1081 \le 数组元素的值\lt 10^8）

第三行，一个整数 qq，代表有要求出 qq 个数首次出现的位置（q≤105q \le 10^5)

第四行，qq 个整数，用空格隔开，代表要找的数（1≤要找的数≤1051 \le 要找的数 \le 10^5）

输出

输出 1 行，含 qq 个整数，按题意输出要找的每个数在数组中最后一次出现的索引位置，如果不存在这样的数，请输出 −1。

输入输出样例

输入数据

6 1 2 2 2 3 3 3 3 2 5

输出数据

5 3 -1

题目解析

确定要选用的模板，因为这个任务是找数字在数组中最后一次出现的位置，也就是找 **≤要找的数字\le 要找的数字**的最右侧的元素。

我们的判断条件就是：中间元素 ≤ 目标元素，则目标元素应该在右半部分，可以将左半部分舍弃掉，需要修正左边界 ，l = mid ，因此选择模板 2 。

实现代码

// 二分查找右边界
#include <iostream>
using namespace std;

const int N = 1e6 + 10;
int q[N], n, k;

// 根据分析选择模板 2
int binary_search(int l, int r, int x) {
  while (l < r) {
    int mid = 1 + (l + r) / 2;
    if (q[mid] <= x) l = mid;
    else r = mid - 1;
  }
  
  if (q[l] != x) return -1;
  else return l;
}

int main() {
    scanf("%d", &n);
    
    for (int i = 0; i < n; i++) scanf("%d", &q[i]);
    
    cin >> k;
    
    while (k--) {
      int x;
      scanf("%d", &x);
      
      int l = 0, r = n - 1;
      
      cout << binary_search(l, r, x) << " ";
    }

    return 0;
}

练习：二分查找数的范围

题目描述

给定一个按照升序排列的长度为 nn 的整数数组，以及 qq 个查询。

对于每个查询，返回一个元素 kk 的起始位置和终止位置（位置从 0 开始计数）。

如果数组中不存在该元素，则返回 -1 -1。

输入描述

第一行包含整数 nn 和 qq，表示数组长度和询问个数。

第二行包含 nn 个整数（均在 1∼10000 范围内），表示完整数组。

接下来 qq 行，每行包含一个整数 kk，表示一个询问元素。

输出描述

共 qq 行，每行包含两个整数，表示所求元素的起始位置和终止位置。

如果数组中不存在该元素，则返回 -1 -1。

数据范围

  • 1≤n≤1000001 \le n \le 100000
  • 1≤q≤100001 \le q \le 10000
  • 1≤k≤100001 \le k \le 10000

输入输出样例

输入数据 1

6 3 1 2 2 3 3 4 3 4 5

输出数据 1

3 4 5 5 -1 -1

题目解析

这个任务是找元素出现的范围，其实也就是把前面两个练习合起来思考的结果，找到元素第一次出现的位置和最后一次出现的位置，不就是得到范围了吗。如下面的示意图所示。

也就是说，我们两个模板都要用到。

代码实现

// 查找数的范围
#include <iostream>
using namespace std;

const int N = 1e6 + 10;
int q[N], n, k;

// 模板 1，确定左边界
int binary_search1(int l, int r, int x) {
  while (l < r) {
    int mid = (l + r) / 2;
    if (q[mid] >= x) r = mid;
    else l = mid + 1;
  }
  
  if (q[l] != x) return -1;
  else return l;
}

// 模板 2，确定右边界
int binary_search2(int l, int r, int x) {
  while (l < r) {
    int mid = 1 + (l + r) / 2;
    if (q[mid] <= x) l = mid;
    else r = mid - 1;
  }
  
  if (q[l] != x) return -1;
  else return l;
}

int main() {
    scanf("%d%d", &n, &k);
    
    for (int i = 0; i < n; i++) scanf("%d", &q[i]);
    
    while (k--) {
      int x;
      scanf("%d", &x);
      
      int l = 0, r = n - 1;
      
      cout << binary_search1(l, r, x) << " " << binary_search2(l, r, x) << endl;
    }

    return 0;
}

STL 中的二分查找函数

在C++标准模板库（STL）中也提供了几个二分查找相关的函数实现，其用法也是大同小异，一旦理解了上面两个模板的实现与用法，直接使用 STL 中的二分查找函数也就很简单了。

  • binary_search(begin, end, value)：检查 value 是否存在于[begin, end)范围内，并返回一个布尔值表示查找结果。
  • lower_bound(begin, end, value)：找到不小于 value 的第一个位置（查找左边界），如果所有元素都大于 value，则返回 end。
  • upper_bound(begin, end, value)：找到不大于 value 的最后一个位置（查找右边界），如果所有元素都小于 value，则返回 begin。

使用 lower_bound() 完成查找左边界的例子。

小结

二分查找算法的思想并不复杂，就是在查找过程通过每次折半，缩小搜索范围，快速逼近目标元素，但在代码实现中有不少边界问题需要注意，很容易出错，因此希望大家能掌握上面的两个算法模板，做到灵活运用。

二分查找算法的前提条件是要求数组是有序的，但允许数组元素重复，如果数组无序，需要先进行排序。

二分查找算法的时间复杂度是 O(log⁡n)O(\log n) ，因此它也是一种非常高效的查找算法。

ON THIS PAGE