1. 二分搜索概述

二分搜索(英语:binary search),也称折半搜索(英语:half-interval search)、对数搜索(英语:logarithmic search),是一种在有序数组中查找某一特定元素的搜索算法。

二分搜索是一种高效的查找算法,适用于在已排序的数组中查找特定元素。它的基本思想是通过不断将搜索区间对半分割,从而快速缩小查找范围。

二分搜索每次把搜索区域减少一半,时间复杂度为 O(logn)(n代表集合中元素的个数)。

二分搜索的基本步骤如下:

  1. 初始条件:将搜索范围设为数组的整个区间。
  2. 查找中间元素:计算当前区间的中间索引。
  3. 比较中间元素:将中间元素与目标值进行比较:
    • 如果中间元素等于目标值,查找成功,返回中间索引。
    • 如果中间元素小于目标值,将搜索范围缩小到右半部分。
    • 如果中间元素大于目标值,将搜索范围缩小到左半部分。
  4. 重复步骤 2 和 3,直到找到目标值或搜索范围为空。

在下图中为大家展示了二分搜索的过程:

image-20240704022709652

2. 递归实现

递归实现二分搜索的代码如下:

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
#include <iostream>
#include <vector>
using namespace std;

int binarySearchRecursive(const vector<int>& arr, int left, int right, int target)
{
if (left <= right)
{
int mid = left + (right - left) / 2;
if (arr[mid] == target)
{
return mid;
}
if (arr[mid] > target)
{
return binarySearchRecursive(arr, left, mid - 1, target);
}
return binarySearchRecursive(arr, mid + 1, right, target);
}
return -1;
}

int main()
{
vector<int> arr = { 2, 3, 4, 10, 40 };
int target = 10;
int result = binarySearchRecursive(arr, 0, arr.size() - 1, target);

if (result != -1)
{
cout << "元素在索引 " << result << " 处找到" << endl;
}
else
{
cout << "元素未找到" << endl;
}

return 0;
}

代码解释

  1. 函数定义binarySearchRecursive 函数接收一个数组 arr、搜索范围的左右边界 leftright,以及目标值 target
  2. 终止条件:当 left 大于 right 时,搜索范围为空,返回 -1 表示未找到目标值。
  3. 计算中间索引:使用 left + (right - left) / 2 计算中间索引,避免溢出。
  4. 比较中间元素:检查中间元素是否等于目标值,如果等于则返回中间索引。
  5. 递归调用:根据中间元素与目标值的大小关系,递归调用函数搜索左半部分或右半部分。

3. 非递归实现

非递归实现二分搜索的代码如下:

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
#include <iostream>
#include <vector>
using namespace std;

int binarySearchIterative(const vector<int>& arr, int target)
{
int left = 0;
int right = arr.size() - 1;

while (left <= right)
{
int mid = left + (right - left) / 2;
if (arr[mid] == target)
{
return mid;
}

else if (arr[mid] > target)
{
right = mid - 1;
}
else
{
left = mid + 1;
}
}
return -1;
}

int main()
{
vector<int> arr = { 2, 3, 4, 10, 40 };
int target = 10;
int result = binarySearchIterative(arr, target);

if (result != -1)
{
cout << "元素在索引 " << result << " 处找到" << endl;
}
else
{
cout << "元素未找到" << endl;
}

return 0;
}

代码解释

  1. 函数定义binarySearchIterative 函数接收一个数组 arr 和目标值 target
  2. 初始化左右边界left 初始化为 0,right 初始化为数组长度减一。
  3. 循环条件:当 left 小于或等于 right 时,继续搜索。
  4. 计算中间索引:使用 left + (right - left) / 2 计算中间索引,避免溢出。
  5. 比较中间元素:检查中间元素是否等于目标值,如果等于则返回中间索引。
  6. 调整边界:根据中间元素与目标值的大小关系,调整左边界或右边界。
  7. 未找到目标值:当循环结束且未找到目标值时,返回 -1。