---
title: "二分算法"
description: "枚举、模拟、贪心、递归、二分、动态规划、图论等经典算法。"
---

> Documentation Index
> Fetch the complete documentation index at: https://cppguide.xyz/llms.txt
> Use this file to discover all available pages before exploring further.

# 二分算法

![](https://img.dailyup.xyz/originals/8208463062071-8f41f74f-8c7a-495d-9e2c-4abc0434809f.png)

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

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

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

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

![](https://img.dailyup.xyz/originals/8208463046882-778e4683-5219-4cb7-bbbf-786a55518046.gif)

## 二分查找

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

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

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

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

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

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

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

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

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

```cpp
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
}
```

需要注意的是：

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

## 示例：二分查找元素

### 题目描述

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

### 输入描述

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

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

### 输出描述

$x$ 在数组中的索引位置，或者 `-1`。

### 输入输出样例

输入数据

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

输出数据

```
6
```

### 实现代码

- [3zjjn25hy - C++ - OneCompiler](https://onecompiler.com/cpp/3zjjn25hy)

```cpp
#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` 代表搜索范围的起始与结束索引，初始值就应该是该数组的第一个元素（索引为 $0$）和最后一个元素的索引值（索引为 $n-1$）。

**第 2 步，确定中间元素**

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

![](https://img.dailyup.xyz/optimized/8208463060016-44828851-85e9-43bf-bb3a-1595caa855f9.png)

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

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

![](https://img.dailyup.xyz/optimized/8208463058531-007eff21-2380-4200-bb54-228f2ffd2e5d.png)

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

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

![](https://img.dailyup.xyz/optimized/8208463056824-4f4a796a-52fd-4745-be12-48a641820e73.png)

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

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

![](https://img.dailyup.xyz/optimized/8208463055391-266582c9-e206-4cbf-8918-11ea8b20ce9e.png)

## 二分查找算法模板

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

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

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

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

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

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

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

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

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

### 二分查找模板 1

```cpp
// 区间被划分为 [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

```cpp
// 区间被划分为 [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 的运算。

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

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

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

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

3. **比较中间元素与目标元素**

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

4. **最后函数的返回值**

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

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

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

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

- [3zjnhp9b5 - C++ - OneCompiler](https://onecompiler.com/cpp/3zjnhp9b5)

```cpp
#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）

- [3zjnhv7nz - C++ - OneCompiler](https://onecompiler.com/cpp/3zjnhv7nz)

```cpp
#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
- 另一个是返回值，这里因为要处理元素不存在的情况，因此我们在返回前做了一次判断。

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

## 练习：二分查找左边界

### 题目描述

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

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

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

### 输入

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

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

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

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

### 输出

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

### 输入输出样例

输入数据

```
6
1 2 2 2 3 3
3
3 2 5
```

输出数据

```
4 1 -1
```

### 题目解析

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

![](https://img.dailyup.xyz/optimized/8208463053673-230b97d1-41e5-4771-a53a-1d6143fdb11b.png)

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

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

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

### 实现代码

- [3zjjr3brg - C++ - OneCompiler](https://onecompiler.com/cpp/3zjjr3brg)

```cpp
// 二分查找左边界
#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;
}
```

## 练习：二分查找右边界

### 题目描述

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

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

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

### 输入

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

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

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

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

### 输出

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

### 输入输出样例

输入数据

```
6
1 2 2 2 3 3
3
3 2 5
```

输出数据

```
5 3 -1
```

### 题目解析

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

![](https://img.dailyup.xyz/optimized/8208463052236-139cc680-1bda-4d02-9049-1d4d39ccd765.png)

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

### 实现代码

- [3zjjzqasw - C++ - OneCompiler](https://onecompiler.com/cpp/3zjjzqasw)

```cpp
// 二分查找右边界
#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;
}
```

## 练习：二分查找数的范围

### 题目描述

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

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

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

### 输入描述

第一行包含整数 $n$ 和 $q$，表示数组长度和询问个数。

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

接下来 $q$ 行，每行包含一个整数 $k$，表示一个询问元素。

### 输出描述

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

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

### 数据范围

- $1 \le n \le 100000$
- $1 \le q \le 10000$
- $1 \le k \le 10000$

### 输入输出样例

输入数据 1
```
6 3
1 2 2 3 3 4
3
4
5
```

输出数据 1

```
3 4
5 5
-1 -1
```

### 题目解析

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

![](https://img.dailyup.xyz/optimized/8208463050186-426f9113-c4ac-4326-9c68-1c4b3999f1a6.png)

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

### 代码实现

- [3zjk33afa - C++ - OneCompiler](https://onecompiler.com/cpp/3zjk33afa)

```cpp
// 查找数的范围
#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)$** ，因此它也是一种非常高效的查找算法。

Source: https://cppguide.xyz/algorithm/bisection/index.mdx