二分查找算法原理与常见变体实战

二分查找算法原理与常见变体实战

二分查找的核心在于利用数据的有序性，通过不断缩小搜索区间来快速定位目标。虽然大家常认为它仅适用于简单的数值查找，但在实际开发中，无论是缓存索引还是参数优化，只要数据具备'二段性'，二分思想都能派上用场。不过，很多开发者容易在边界处理上出错，导致死循环或越界。下面结合几个经典场景，梳理一下二分查找的实现细节。

算法原理与模板

二分的本质不是简单的折半，而是根据目标值与中间值的比较关系，排除掉一半不可能包含目标的区间。针对不同需求（如找左端点、右端点），我们需要微调 mid 的计算方式和收缩策略。

基础查找

最基础的二分查找用于判断目标是否存在。关键在于循环条件 left <= right 以及 mid 的取整方式。

int left = 0, right = nums.size() - 1;
while (left <= right) {
    int mid = left + (right - left) / 2;
    if (nums[mid] == target) return mid;
    else if (nums[mid] > target) right = mid - 1;
    else left = mid + 1;
}
return -1;

寻找目标范围

当数组中存在重复元素时，我们需要找到目标值出现的起始和结束位置。这可以看作两次独立的二分查找：一次找左边界，一次找右边界。

找左边界时，如果 mid 落在目标左侧，说明目标在右边，left = mid + 1；如果 mid 落在目标或其右侧，right = mid，注意此时不能跳过 mid。

找右边界则相反，如果 mid 落在目标右侧，right = mid - 1；如果 mid 落在目标或其左侧，left = mid。为了避免死循环，mid 计算需向上取整。

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        if (nums.empty()) return {-1, -1};
        int left = 0, right = nums.size() - 1;
        int start = -1, end = -1;

        // 找左端点
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] >= target) right = mid;
            else left = mid + 1;
        }
        if (nums[left] == target) start = left;

        // 找右端点
        left = 0; right = nums.size() - 1;
        while (left < right) {
            int mid = left + (right - left + 1) / 2;
            if (nums[mid] <= target) left = mid;
            else right = mid - 1;
        }
        if (nums[left] == target) end = left;

        return {start, end};
    }
};

搜索插入位置

如果目标不存在，需要返回它应该插入的位置。这其实也是寻找第一个大于等于目标值的位置。

class Solution {
public:
    int searchInsert(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) right = mid;
            else left = mid + 1;
        }
        return nums[left] < target ? left + 1 : left;
    }
};

旋转排序数组中的最小值

对于旋转过的有序数组，依然可以利用二分查找的特性。数组被分为两段递增序列，最小值位于转折点。我们可以通过比较 mid 与 nums[0] 的关系来判断 mid 落在哪一段。

class Solution {
public:
    int findMin(vector<int>& nums) {
        int left = 0, right = nums.size();
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] >= nums[0]) left = mid + 1;
            else right = mid;
        }
        return left == nums.size() ? nums[0] : nums[left];
    }
};

以上几种变体涵盖了二分查找在面试和实战中的主要应用场景。掌握边界条件的判断逻辑，比死记硬背模板更重要。