二分搜索要求容器有序，通过比较中间值缩小范围，时间复杂度O(log n)。可用递归或迭代实现，推荐迭代以节省栈空间。C++ STL提供binary_search、lower_bound和upper_bound等函数，实际开发建议优先使用STL版本，更安全高效。
在C++中实现二分搜索，前提是数组或容器必须是有序的。二分搜索通过不断缩小查找范围，将时间复杂度从线性搜索的O(n)降低到O(log n)。
基本思路
二分搜索的核心思想是：比较目标值与当前搜索区间的中间元素，根据比较结果决定向左或右继续搜索。
- 定义两个指针，left 和 right，表示当前搜索区间
- 计算中间位置：mid = left + (right – left) / 2（避免整数溢出）
- 如果中间值等于目标，返回索引
- 如果中间值小于目标，搜索右半部分
- 如果中间值大于目标，搜索左半部分
- 循环直到 left > right，未找到则返回-1
递归实现方式
int binarySearchRecursive(const vector<int>& arr, int left, int right, int target) {
if (left > right) return -1;
<pre class='brush:php;toolbar:false;'>int mid = left + (right - left) / 2;
if (arr[mid] == target) return mid;
else if (arr[mid] < target)
return binarySearchRecursive(arr, mid + 1, right, target);
else
return binarySearchRecursive(arr, left, mid - 1, target);
}
纳米搜索
30
纳米搜索：360推出的新一代AI搜索引擎
30
查看详情
调用时传入初始区间：binarySearchRecursive(arr, 0, arr.size() – 1, target);
立即学习“C++免费学习笔记（深入）”；
迭代实现方式（推荐）
int binarySearchIterative(const vector<int>& arr, int target) {
int left = 0;
int right = arr.size() - 1;
<pre class='brush:php;toolbar:false;'>while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) return mid;
else if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1; // 未找到
}
迭代方式更节省栈空间，不易发生递归溢出，适合大规模数据。
使用STL中的二分搜索函数
C++标准库提供了几个高效的二分搜索函数，定义在 <algorithm> 头文件中：
- std::binary_search：判断元素是否存在，返回bool
- std::lower_bound：返回第一个不小于target的元素位置
- std::upper_bound：返回第一个大于target的元素位置
示例：
vector<int> arr = {1, 3, 5, 7, 9};
bool found = binary_search(arr.begin(), arr.end(), 5); // true
auto it = lower_bound(arr.begin(), arr.end(), 6); // 指向7
int index = it - arr.begin(); // 索引为3
基本上就这些。手动实现有助于理解原理，实际开发中建议优先使用STL函数，更安全高效。
相关标签：
go 栈 c++ 标准库 递归 循环 指针 栈
大家都在看：
cgo与Objective-C互操作：解决Go 1.1版本中的链接问题
深入理解Go程序执行：go run与go build的差异与应用
Go语言中如何判断 interface{} 是否为任意类型的 Map
Go语言中SVG到图像的转换：利用外部工具实现
使用Go语言实现高效的并行URL请求与超时控制
深入理解Go程序执行：go run与go build的差异与应用
Go语言中如何判断 interface{} 是否为任意类型的 Map
Go语言中SVG到图像的转换：利用外部工具实现
使用Go语言实现高效的并行URL请求与超时控制
本站资料仅供学习交流使用请勿商业运营，严禁从事违法，侵权等任何非法活动，否则后果自负！
THE END
暂无评论内容