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

流程解析

20. 搜索插入位置

题目描述

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

题目示例

输入: [1,3,5,6], target: 5 输出: 2

输入: [1,3,5,6], target: 2 输出: 1

解法思路

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

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

设 left 和 right 分别为当前查询区间的左右边界。根据中间值 nums[mid] 与 target 的比较结果，我们可以收缩区间：

1. 当 nums[mid] >= target 时，mid 落在了 [index, right] 区间上。mid 左边包括 mid 本身可能是最终结果，所以下一轮查找区间为 [left, mid]。此时更新 right = mid。
2. 当 nums[mid] < target 时，mid 落在了 [left, index-1] 区间上。mid 右边但不包括 mid 本身可能是结果，所以下一轮查找区间为 [mid+1, right]。此时更新 left = mid + 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;
            }
        }
        
        // 处理目标值大于数组最大值的情况
        if (target > nums[nums.size() - 1]) {
            return left + 1;
        }
        return left;
    }
};

流程解析