二分查找实战：x 的平方根与搜索插入位置解析

20. 搜索插入位置

题目描述

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

解题思路

我们需要确定插入位置的坐标 index。分析插入位置左右两侧区间上元素的特点：

• 区间 [left, index-1] 内所有元素均小于 target；
• 区间 [index, right] 内所有元素均大于等于 target。

根据 mid 位置元素的信息，分析下一轮查询的区间：

1. 当 nums[mid] >= target 时，说明 mid 落在了 [index, right] 区间上。mid 左边包括 mid 本身可能是最终结果，因此新 right 到 mid 位置，继续查找。
2. 当 nums[mid] < target 时，说明 mid 落在了 [left, index-1] 区间上。mid 右边但不包括 mid 本身可能是最终结果，因此更新 left 到 mid + 1 的位置，继续查找。

直到查找区间的长度变为 1，也就是 left == right 的时候，left 或者 right 所在的位置就是我们要找的结果。

代码实现

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] >= target) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        
        // 处理边界情况：如果 target 大于数组最后一个元素
        if (target > nums[nums.size() - 1]) {
            return left + 1;
        }
        
        return left;
    }
};

关键点总结

这道题的核心在于理解'左闭右开'或'左闭右闭'区间在二分查找中的收敛逻辑。特别是当目标值大于所有元素时，需要单独判断，否则直接返回 left 可能会导致越界或索引错误。

通过这两道题，我们复习了二分查找在不同场景下的变体应用。实际编码中，务必留意整数溢出风险以及边界条件的特殊处理。