- 二分搜索概述 {#1-二分搜索概述}
二分搜索 (英语:binary search),也称折半搜索 (英语:half-interval search)、对数搜索(英语:logarithmic search),是一种在有序数组中查找某一特定元素的搜索算法。
二分搜索是一种高效的查找算法,适用于在已排序的数组中查找特定元素。它的基本思想是通过不断将搜索区间对半分割,从而快速缩小查找范围。
二分搜索每次把搜索区域减少一半,时间复杂度为 O(log~n~)(n代表集合中元素的个数)。
二分搜索的基本步骤如下:
- 初始条件:将搜索范围设为数组的整个区间。
- 查找中间元素:计算当前区间的中间索引。
- 比较中间元素 :将中间元素与目标值进行比较:
- 如果中间元素等于目标值,查找成功,返回中间索引。
- 如果中间元素小于目标值,将搜索范围缩小到右半部分。
- 如果中间元素大于目标值,将搜索范围缩小到左半部分。
- 重复步骤 2 和 3,直到找到目标值或搜索范围为空。
在下图中为大家展示了二分搜索的过程:
- 递归实现 {#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; }
|
代码解释 {#代码解释}
-
函数定义 :
binarySearchRecursive
函数接收一个数组arr
、搜索范围的左右边界left
和right
,以及目标值target
。 -
终止条件 :当
left
大于right
时,搜索范围为空,返回 -1 表示未找到目标值。 -
计算中间索引 :使用
left + (right - left) / 2
计算中间索引,避免溢出。 -
比较中间元素:检查中间元素是否等于目标值,如果等于则返回中间索引。
-
递归调用:根据中间元素与目标值的大小关系,递归调用函数搜索左半部分或右半部分。
-
非递归实现 {#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
。 - 初始化左右边界 :
left
初始化为 0,right
初始化为数组长度减一。 - 循环条件 :当
left
小于或等于right
时,继续搜索。 - 计算中间索引 :使用
left + (right - left) / 2
计算中间索引,避免溢出。 - 比较中间元素:检查中间元素是否等于目标值,如果等于则返回中间索引。
- 调整边界:根据中间元素与目标值的大小关系,调整左边界或右边界。
- 未找到目标值:当循环结束且未找到目标值时,返回 -1。