LeetCode 搜索插入位置：二分查找边界处理

题目大意

给定升序无重复数组 nums 和目标值 target，返回目标索引（若存在）或应插入位置（保持有序）。

二分查找模板

public class SearchInsert {
    public int searchInsert(int[] nums, int target) {
        int lo = 0, hi = nums.length - 1;
        // 边界预判
        if (target <= nums[0]) return 0;
        if (target > nums[hi]) return hi + 1;
        // 标准二分
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (nums[mid] == target) return mid;
            else if (nums[mid] < target) lo = mid + 1;
            else hi = mid - 1;
        }
        // 循环结束 lo = hi + 1，lo 即插入位置
        return lo;
    }
}

关键点

1. 边界预判：避免 mid±1 越界
2. 循环不变量：[0,lo) < target，(hi, n-1] > target
3. 返回 lo：退出时 lo = hi+1，恰为第一个 ≥ target 的位置

C++ 版本

int searchInsert(vector& nums, int target) {
    int lo = 0, hi = nums.size() - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] >= target) hi = mid - 1;
        else lo = mid + 1;
    }
    return lo;
}

复杂度

• 时间：O(log n)
• 空间：O(1)

扩展：下界/上界

• lower_bound：首个 ≥ target（即本题答案）
• upper_bound：首个 > target
• C++ STL：lower_bound(nums.begin(), nums.end(), target) - nums.begin()