二分查找用于在有序数组中高效查找目标值，时间复杂度O(log n)。核心思想是每次缩小一半搜索区间，需满足数组有序且支持随机访问。标准写法使用闭区间[left, right]，循环条件为left target）等函数，可简化实现。面试关键在于明确查找目标（任意位置或边界）、正确处理区间开闭与边界更新，防止死循环。掌握标准写法与两种边界变体，并熟悉STL函数，足以应对大多数面试题。
二分查找是一种在有序数组中快速定位目标值的高效算法，时间复杂度为 O(log n)，是 C++ 面试中最常考的基础算法之一。掌握其写法和边界处理技巧至关重要。
基本思路与适用条件
二分查找的核心思想是每次将搜索区间缩小一半：
数组必须是已排序的（默认升序）支持随机访问（数组或 vector）查找某个值是否存在、位置，或满足某种条件的边界
标准二分查找写法
查找目标值 target 的下标，若不存在返回 -1：
int binarySearch(vector& nums, int target) { int left = 0; int right = nums.size() - 1; // 注意：闭区间while (left <= right) { int mid = left + (right - left) / 2; // 防止溢出 if (nums[mid] == target) { return mid; } else if (nums[mid] < target) { left = mid + 1; } else { right = mid - 1; }}return -1;
}
立即学习“C++免费学习笔记（深入）”；
常见变体：查找左边界
当存在重复元素时，查找第一个等于 target 的位置：
int leftBound(vector& nums, int target) { int left = 0; int right = nums.size() - 1; int result = -1;while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] == target) { result = mid; right = mid - 1; // 继续向左找 } else if (nums[mid] < target) { left = mid + 1; } else { right = mid - 1; }}return result;
}
立即学习“C++免费学习笔记（深入）”；
常见变体：查找右边界
查找最后一个等于 target 的位置：
int rightBound(vector& nums, int target) { int left = 0; int right = nums.size() - 1; int result = -1;while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] == target) { result = mid; left = mid + 1; // 继续向右找 } else if (nums[mid] < target) { left = mid + 1; } else { right = mid - 1; }}return result;
}
立即学习“C++免费学习笔记（深入）”；
STL 中的二分查找函数
C++ 标准库提供了几个高效的二分查找函数，面试中可简要提及：
std::binary_search：判断元素是否存在std::lower_bound：返回第一个 ≥ target 的迭代器std::upper_bound：返回第一个 > target 的迭代器
例如：
vector nums = {1, 2, 2, 2, 3, 4};auto it = lower_bound(nums.begin(), nums.end(), 2);int index = it - nums.begin(); // 返回 1
面试注意事项
写二分查找时容易出错的地方：
循环条件是 left 还是 mid 计算用 left ，取决于区间开闭left + (right - left) / 2 避免整数溢出更新 left 和 right 时是否漏掉 ±1，防止死循环明确题目是要找“任意位置”还是“边界位置”
基本上就这些。掌握标准写法和两个边界变体，再熟悉 STL 函数，应对 C++ 面试中的二分查找题就足够了。关键是逻辑清晰，边界处理正确。
以上就是C++ 二分查找算法怎么写_C++算法面试高频题解析的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1487081.html
微信扫一扫 
支付宝扫一扫 
