二分搜索
二分搜索（Binary Search），也叫折半查找，是一种在有序数组中查找特定元素的高效搜索算法。
它的核心思想非常直观：每次都将搜索范围缩小一半，直到找到目标元素或搜索范围为空。
核心原理和前提条件
二分搜索基于“分治法”思想，不断排除不存在目标值的一半区间，实现快速定位。
使用二分搜索，我们需要保证数据是有序的，如果数据无序，必须先排序才能使用二分查找。
时间与空间复杂度分析
| 复杂度类型 | 时间复杂度 | 说明 |
|---|---|---|
| 最优情况 | O(1) | 目标值恰好是数组的第一个中间元素。 |
| 最坏/平均情况 | O(\log n) | 每次都将搜索范围减半，对于长度为 n 的数组，最多只需查找 \log_2 n 次。 |
| 空间复杂度 | O(1) | 只使用了常数级别的额外空间（几个变量）。 |
所需参数
| 参数 | 含义 | 备注 |
|---|---|---|
*nums | 搜索对象所在数组 | 一串有序数据，需要提前排好序 |
numsSize | 数组 nums 的长度，及数据个数 | 如果语言可以自己得到，也不一定需要用户输入，只是函数需要这个数据 |
target | 搜索对象 | 故事的主角，我们的目的就是得到它的位置 |
思路 && 步骤
已知数组 *nums 和数组长度 numsSize 以及所需寻找的对象 target。在数组 *nums 是有序数组的前提下，我们检查 numsSize/2 位置处的数据。以数组是升序为例，若 nums[numsSize/2] 大于 target, 我们便宣判：我们寻找的数不在 numsSize/2 的右边（应为它们更大）。我们便继续以 0 为开头 numsSize/2 - 1 为结尾，检查它们中间位置的数据（我们以 mid 代指）。若 mid 小于 target，我们便接着以 mid 为开头、numsSize/2 - 1 为结尾，继续寻找target。
根据这个思路，我们可以使用两种方法实现：递归和循环
递归
==需要注意的是，虽然递归在构建思路的时候比循环方便，但占用的资源不是循环可以比的，并且，如果递归会出现分支的话（一次调用好几次自己），还会出现重复运算。并不推荐依赖递归。==
首先，我们需要先用递归的基本思路，判断三个要点：
- 终止条件：找到目标数据，或者检索区域全部排除。
- 递归关系：当mid位置不是目标数据时，调用自己。
- 递归公式：调用自己的具体方法和步骤。
以此，我们可以先这样：
int binarySearch(int *nums, int l,int r,int target){
if(l >= r) return -1; // 检索区全部排除
int mid = (r + l) / 2;
if(nums[mid] == target) return mid; // 找到目标数据
// todo 判断条件
}
确认终止条件之后，我们需要思考递归公式。
及mid的数据不是target（以下简称为t）时，我们判断mid所在数据（以下简称m）与t的大小。还是以升序为例,如果m<t,我们可以判断：t不在mid之前，及我们只需要检查mid+1到r的部分就可以了。反过来，思路也一样。
// todo 判断条件
if (nums[mid] < target) return binarySearch(nums, mid + 1, r, target);
else return binarySearch(nums, l, mid - 1, target);
完整代码如下：
#include <bits/stdc++.h>
using namespace std;
int binarySearch(int *nums, int l,int r,int target){
if(l >= r) return -1; // 检索区全部排除
int mid = l + (r - l) / 2; // 修正：防止整数溢出
if(nums[mid] == target) return mid; // 找到目标数据
// todo 判断条件
if (nums[mid] < target) return binarySearch(nums, mid + 1, r, target);
else return binarySearch(nums, l, mid - 1, target);
}
int main()
{
// 测试代码示例
int nums[] = {1, 3, 5, 7, 9, 11, 13, 15};
int target = 7;
int size = sizeof(nums) / sizeof(nums[0]);
int result = binarySearch(nums, 0, size - 1, target);
if(result != -1) {
cout << "找到了目标值 " << target << "，位于索引 " << result << endl;
} else {
cout << "未找到目标值 " << target << endl;
}
return 0;
}
循环
仔细观察会发现，我们需要一直重复确认rl和判断mid的操作。我们可以把重复的部分使用循环封装起来：
while(l <= r){
int mid = (r + l) / 2;
if (nums[mid] == target) return mid;
if (nums[mid] < target) l = mid + 1;
else r = mid - 1;
}
然后实现其他功能，例如封装到函数里：
#include <bits/stdc++.h>
using namespace std;
int binarySearch(int *nums, int l,int r,int target){
while(l <= r){
int mid = l + (r - l) / 2;
if(nums[mid] == target){
return mid;
}else if(nums[mid] < target){
l = mid + 1;
}else{
r = mid - 1;
}
}
return -1;
}
int main()
{
// 测试代码示例
int nums[] = {1, 3, 5, 7, 9, 11, 13, 15};
int target = 7;
int size = sizeof(nums) / sizeof(nums[0]);
int result = binarySearch(nums, 0, size - 1, target);
if(result != -1) {
cout << "找到了目标值 " << target << "，位于索引 " << result << endl;
} else {
cout << "未找到目标值 " << target << endl;
}
return 0;
}
总结
循环和递归在解决二分搜索问题时思路本质上是一致的，都遵循相同的分治策略：通过比较中间元素来决定搜索方向，逐步缩小搜索范围。
两者的主要区别：
-
实现方式：
- 递归：通过函数自调用实现，代码更简洁直观
- 循环：通过
while循环控制，避免函数调用开销
-
性能考量：
- 递归：存在函数调用栈开销，可能导致栈溢出风险
- 循环：空间复杂度更优，无额外栈空间消耗
-
编码实践：
- 可以先用递归思维分析问题（分解为子问题）
- 再用循环方式实现以获得更好的性能
在实际开发中，推荐使用循环实现 binarySearch 函数，既保证了代码效率，又具备良好的可读性。