<p>二分查找用于在有序数组中高效查找目标值，时间复杂度O(log n)。核心思想是每次缩小一半搜索区间，需满足数组有序且支持随机访问。标准写法使用闭区间[left, right]，循环条件为left <= right，通过mid = left + (right - left) / 2计算中点，避免整数溢出。若nums[mid] == target则返回下标；小于则搜索右半区，left = mid + 1；大于则搜索左半区，right = mid - 1。常见变体包括查找左边界和右边界：查找第一个等于target的位置时，命中后不立即返回，而是记录result = mid并继续向左搜索（right = mid - 1）；查找最后一个位置则继续向右搜索（left = mid + 1）。C++ STL提供binary_search、lower_bound（首个≥target）、upper_bound（首个>target）等函数，可简化实现。面试关键在于明确查找目标（任意位置或边界）、正确处理区间开闭与边界更新，防止死循环。掌握标准写法与两种边界变体，并熟悉STL函数，足以应对大多数面试题。</p>
二分查找是一种在有序数组中快速定位目标值的高效算法，时间复杂度为 O(log n)，是 C++ 面试中最常考的基础算法之一。掌握其写法和边界处理技巧至关重要。
基本思路与适用条件
二分查找的核心思想是每次将搜索区间缩小一半：
- 数组必须是已排序的（默认升序）
- 支持随机访问（数组或 vector）
- 查找某个值是否存在、位置，或满足某种条件的边界
标准二分查找写法
查找目标值 target 的下标，若不存在返回 -1：
int binarySearch(vector<int>& nums, int target) {
int left = 0;
int right = nums.size() - 1; // 注意：闭区间
<pre class='brush:php;toolbar:false;'>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<int>& nums, int target) {
int left = 0;
int right = nums.size() - 1;
int result = -1;
<pre class='brush:php;toolbar:false;'>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<int>& nums, int target) {
int left = 0;
int right = nums.size() - 1;
int result = -1;
<pre class='brush:php;toolbar:false;'>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<int> nums = {1, 2, 2, 2, 3, 4};
auto it = lower_bound(nums.begin(), nums.end(), 2);
int index = it - nums.begin(); // 返回 1
面试注意事项
写二分查找时容易出错的地方：
- 循环条件是
left <= right还是left < right，取决于区间开闭 - mid 计算用
left + (right - left) / 2避免整数溢出 - 更新 left 和 right 时是否漏掉 ±1，防止死循环
- 明确题目是要找“任意位置”还是“边界位置”
基本上就这些。掌握标准写法和两个边界变体，再熟悉 STL 函数，应对 C++ 面试中的二分查找题就足够了。关键是逻辑清晰，边界处理正确。
