二分查找在有序数组中以O(log n)时间复杂度快速定位目标值，通过维护left和right指针，计算mid = left + (right – left) / 2避免溢出，比较arr[mid]与target决定搜索区间，迭代或递归实现，C++ STL提供binary_search、lower_bound、upper_bound等函数简化操作，使用时需确保数组有序并正确处理边界条件。
二分查找是一种在有序数组中快速查找目标值的高效算法，时间复杂度为 O(log n)。它通过不断缩小搜索范围，将问题规模每次减半，从而实现快速定位。C++ 中可以使用标准库函数，也可以手动实现。下面详细介绍其原理和代码实现。
二分查找基本原理
二分查找的前提是数组必须有序（升序或降序）。算法核心思想如下：
设定两个指针，left 指向数组起始位置，right 指向末尾位置。计算中间位置 mid = left + (right – left) / 2，防止整数溢出。比较 arr[mid] 与目标值 target：若相等，返回 mid；若 arr[mid] 若 arr[mid] > target，说明目标在左半部分，更新 right = mid – 1。循环上述过程直到 left 超过 right，表示未找到，返回 -1。
手写二分查找代码（递归与迭代）
1. 迭代版本（推荐，效率高）
#include #include using namespace std;int binarySearch(vector& 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) { left = mid + 1; } else { right = mid - 1; }}return -1; // 未找到
}
立即学习“C++免费学习笔记（深入）”；
// 示例调用int main() {vector nums = {1, 3, 5, 7, 9, 11, 13};int index = binarySearch(nums, 7);if (index != -1)cout
2. 递归版本
int binarySearchRecursive(vector& arr, int target, int left, int right) { if (left > right) return -1;int mid = left + (right - left) / 2;if (arr[mid] == target) return mid;else if (arr[mid] < target) return binarySearchRecursive(arr, target, mid + 1, right);else return binarySearchRecursive(arr, target, left, mid - 1);
}
立即学习“C++免费学习笔记（深入）”；
// 调用方式：binarySearchRecursive(nums, 7, 0, nums.size()-1);
C++ 标准库中的二分查找
C++ STL 提供了多个用于二分查找的函数，定义在 gorithm> 头文件中：
std::binary_search：判断元素是否存在，返回 bool。std::lower_bound：查找第一个大于等于 target 的位置，返回迭代器。std::upper_bound：查找第一个大于 target 的位置。std::equal_range：返回一对迭代器，表示所有等于 target 的元素范围。
示例：
#include #include #include using namespace std;int main() {vector nums = {1, 3, 5, 7, 7, 7, 9, 11};
// 判断是否存在bool found = binary_search(nums.begin(), nums.end(), 7);// 查找第一个 >=7 的位置auto it1 = lower_bound(nums.begin(), nums.end(), 7);cout << "lower_bound at: " << (it1 - nums.begin()) <7 的位置auto it2 = upper_bound(nums.begin(), nums.end(), 7);cout << "upper_bound at: " << (it2 - nums.begin()) << endl;return 0;
}
立即学习“C++免费学习笔记（深入）”；
使用 STL 函数能减少出错概率，尤其在处理边界情况时更安全。
注意事项与常见错误
确保数组已排序，否则结果不可预测。mid 计算使用 left + (right - left) / 2 防止 left+right 溢出。循环条件为 left 更新边界时避免死循环，如不要写成 mid 而应是 mid±1。
基本上就这些。掌握二分查找对刷题和实际开发都很有帮助，理解逻辑比死记代码更重要。
以上就是c++++ 二分查找代码 c++二分查找算法详解的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1487946.html
微信扫一扫 
支付宝扫一扫 
