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

解题思路

同样是二分查找的经典应用。我们需要确定 target 应该落在哪个区间：

• 若 nums[mid] >= target，说明 mid 及其左侧可能是插入点，收缩右边界至 mid；
• 若 nums[mid] < target，说明插入点在 mid 右侧，左边界移至 mid + 1。

当 left == right 时循环结束，此时 left 指向的就是第一个大于等于 target 的位置。不过要注意一种特殊情况：如果 target 比数组最后一个元素还大，直接插在末尾即可，代码里做了额外判断以防越界。

参考实现

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;
    }
};

流程解析