二分查找适用于有序数组，通过比较中间值缩小范围，时间复杂度O(log n)。可手动实现循环或递归版本，也可使用C++ STL的binary_search、lower_bound等函数。注意数组有序、防溢出计算mid、正确设置边界和循环条件。
二分查找是一种高效的查找算法，适用于已排序的数组。它通过不断缩小查找范围，将时间复杂度从线性查找的 O(n) 降低到 O(log n)。在 C++ 中实现二分查找，既可以使用手动编写循环或递归的方式，也可以借助标准库函数。
基本原理与实现思路
二分查找的核心思想是：在有序数组中，取中间元素与目标值比较：
如果中间元素等于目标值，返回其下标。如果中间元素大于目标值，说明目标在左半部分。如果中间元素小于目标值，说明目标在右半部分。
重复这个过程，直到找到目标或搜索区间为空。
手动实现二分查找（循环版本）
#include #include using namespace std;int binarySearch(const 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 target = 7;int result = binarySearch(nums, target);
if (result != -1) { cout << "元素 " << target << " 在索引 " << result << " 处找到。n";} else { cout << "元素 " << target << " 未找到。n";}return 0;
}
立即学习“C++免费学习笔记（深入）”；
使用 C++ 标准库函数
C++ STL 提供了多个与二分查找相关的算法，定义在 gorithm> 头文件中：
binary_search(first, last, val)：判断 val 是否存在于 [first, last) 区间。lower_bound(first, last, val)：返回第一个不小于 val 的元素位置。upper_bound(first, last, val)：返回第一个大于 val 的元素位置。
#include #include #include using namespace std;int main() {vector nums = {1, 3, 5, 7, 9, 11, 13};int target = 7;
if (binary_search(nums.begin(), nums.end(), target)) { cout << "元素存在。n";}auto it = lower_bound(nums.begin(), nums.end(), target);if (it != nums.end() && *it == target) { cout << "元素在索引 " << (it - nums.begin()) << " 处。n";}return 0;
}
立即学习“C++免费学习笔记（深入）”；
注意事项与常见问题
使用二分查找时要注意以下几点：
数组必须是有序的，否则结果不可预测。计算 mid 时使用 left + (right - left) / 2 可避免整数溢出。循环条件是 left ，等号不能省略，否则可能漏掉最后一个元素。更新边界时注意不要跳过潜在解，比如 left = mid + 1 和 right = mid - 1 是安全的。
基本上就这些。掌握手动实现和标准库用法，能应对大多数查找场景。
以上就是C++怎么实现一个二分查找算法_C++算法入门与有序数组查找的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1486567.html
微信扫一扫 
支付宝扫一扫 
