二分查找要求数据有序，通过递归或迭代实现O(log n)高效搜索，C++ STL提供binary_search、lower_bound等函数推荐优先使用。
在C++中实现二分查找，核心前提是数组或容器中的元素必须是有序排列的。二分查找通过不断缩小搜索范围，将时间复杂度从线性查找的 O(n) 降低到 O(log n)，非常适合处理大规模有序数据。
基本二分查找（递归实现）
递归方式直观地体现二分思想：每次比较中间元素，根据大小决定向左或右继续查找。
#include <iostream>
#include <vector>
<p>int binarySearchRecursive(const std::vector<int>& arr, int left, int right, int target) {
if (left > right) return -1; // 未找到</p><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, left, mid - 1, target);
else
return binarySearchRecursive(arr, mid + 1, right, target);}
非递归（迭代）实现
迭代方式更节省空间，避免递归调用栈开销，实际开发中更常用。
立即学习“C++免费学习笔记（深入）”；
int binarySearchIterative(const std::vector<int>& arr, int target) {
int left = 0, 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) right = mid - 1;
else left = mid + 1;
}
return -1; // 未找到}
使用STL中的二分查找函数
C++标准库提供了现成的二分查找工具，简洁且高效，推荐优先使用。
- std::binary_search：只判断元素是否存在，返回 bool 值
- std::lower_bound：返回第一个不小于 target 的位置
- std::upper_bound：返回第一个大于 target 的位置
#include <algorithm>
<p>bool found = std::binary_search(arr.begin(), arr.end(), target);</p><p>auto it = std::lower_bound(arr.begin(), arr.end(), target);
if (it != arr.end() && *it == target) {
int index = it - arr.begin(); // 获取下标
}</p>基本上就这些。手动实现有助于理解原理，但在实际项目中建议直接使用 STL 函数，减少出错概率，提升开发效率。注意确保数据有序，否则结果不可靠。
