二分查找算法详解与经典例题实战

2. 在排序数组中查找元素的第一个和最后一个位置

题目描述

给定非递减顺序排列的整数数组 nums 和目标值 target，找出目标值的开始位置和结束位置。若不存在返回 [-1, -1]。要求时间复杂度 O(log n)。

实现思路

此题本质是寻找区间的左右边界。需要分别执行两次二分查找：

找左边界： 维护区间 [left, k-1] 小于 target，[k, right] 大于等于 target。 当 nums[mid] < target 时，舍弃左半段，left = mid + 1。 当 nums[mid] >= target 时，保留 mid 作为候选，right = mid。 注意此处使用向下取整，避免死循环。

找右边界： 维护区间 [left, k] 小于等于 target，[k+1, right] 大于 target。 当 nums[mid] <= target 时，保留 mid，left = mid。 当 nums[mid] > target 时，舍弃右半段，right = mid - 1。 注意此处使用向上取整，即 mid = left + (right - left + 1) / 2。

实现代码

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int n = nums.size();
        if (n == 0) return {-1, -1};
        
        // 找左边界
        int left = 0, right = n - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) 
                left = mid + 1;
            else 
                right = mid;
        }
        int Left = 0;
        if (nums[left] != target) return {-1, -1};
        else Left = left;
        
        // 找右边界
        left = 0; right = n - 1;
        while (left < right) {
            int mid = left + (right - left + 1) / 2;
            if (nums[mid] <= target) 
                left = mid;
            else 
                right = mid - 1;
        }
        return {Left, left};
    }
};

小技巧：循环条件中有 -1 时，取整建议 +1；反之无 +1。这能有效避免死循环。

3. 搜索插入位置

题目描述

给定排序数组和目标值，找到目标值索引。若不存在，返回应插入的位置。要求 O(log n)。

实现思路

可转化为寻找大于等于目标值的最左端下标。复用左边界查找模板即可。

实现代码

代码一

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

代码二

class Solution {
public:
    int searchInsert(vector<int>& a, int value) {
        int L = 0, R = a.size() - 1;
        if (a[a.size() - 1] < value) return a.size();
        int index = -1;
        while (L <= R) {
            int mid = L + ((R - L + 1) >> 1);
            if (a[mid] >= value) {
                index = mid;
                R = mid - 1;
            } else {
                L = mid + 1;
            }
        }
        return index;
    }
};

4. x 的平方根

题目描述

计算非负整数 x 的算术平方根，结果只保留整数部分。不得使用内置指数函数。

实现思路

求小于等于 sqrt(x) 的最大整数。同样利用二分法，注意 mid * mid 可能溢出，需使用 long long。

实现代码

代码一

class Solution {
public:
    int mySqrt(int x) {
        int left = 1, right = x;
        if (x < 1) return 0;
        while (left < right) {
            long long mid = left + (right - left + 1) / 2;
            if (mid * mid <= x) 
                left = mid;
            else 
                right = mid - 1;
        }
        return left;
    }
};

代码二

class Solution {
public:
    int mySqrt(int x) {
        int left = 1, right = x;
        if (x < 1) return 0;
        int index = -1;
        while (left <= right) {
            long long mid = left + (right - left + 1) / 2;
            if (mid * mid <= x) {
                index = mid;
                left = mid + 1;
            } else 
                right = mid - 1;
        }
        return index;
    }
};