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

时间复杂度：O(logn)，空间复杂度：O(1)。

020 搜索插入位置

2.1 算法思路——二分查找

1. 分析插入位置左右两侧区间上元素的特点。 设插入位置的坐标为 index，根据插入位置的特点可以知道：

   （1）[left, index-1] 内的所有元素均是小于 target 的； （2）[index, right] 内的所有元素均是大于等于 target 的。

2. 设 left 为本轮查询的左边界，right 为本轮查询的右边界。根据 mid 位置元素的信息，分析下一轮查询的区间：

   （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 的位置，继续查找。

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

2.2 算法实现

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

left 和 right 这里已经相遇了，返回 left 或者 right 都是可以的：

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

时间复杂度：O(logn)，空间复杂度：O(1)