二分查找算法实战:7 道经典题目详解
1. 标准二分查找 (LeetCode 704)
算法原理
二分查找的核心在于数组的二段性。虽然常说是'数组有序',但本质是存在一个分界点,能通过一次比较筛选掉一半区间。
循环结束条件
当 left > right 时结束。因为即使 left == right,仍需与目标值比较一次以确认是否存在。
时间复杂度 O(logN) 对比 O(N) 效率差异巨大。在 int 范围内,O(N) 最多约 4×10^9 次比较,而 O(logN) 仅需 32 次。
数据溢出处理
计算中点时,(left + right) / 2 在极端情况下可能溢出。推荐写法:
int mid = left + (right - left) / 2;
利用起始值加偏移量,既避免溢出又保持结果一致。关于是否加 1(如 (left + right + 1) / 2),奇数长度无影响;偶数长度仅决定取左中位还是右中位,不影响最终收敛结果。
代码实现
class Solution {
public:
int search(vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) left = mid + 1;
else if (nums[mid] > target) right = mid - 1;
else return mid;
}
return -1;
}
};
2. 查找元素的第一个和最后一个位置 (LeetCode 34)
非递减顺序即递增或不变序列。
算法原理
数组具有二段性,可用特定值划分区间。需分别寻找左端点和右端点。







