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

1.2.1 算法思路

设 x 的平方根的最终结果为 index——

1、分析 index 左右两次数据的特点：

（1）[ 0 , index ] 之间的元素，平方之后都是小于等于 x 的； （2）[ index + 1 , x] 之间的元素，平方之后都是大于的。

因此可以使用二分查找算法。

1.2.2 算法实现

代码演示如下——

class Solution {
public:
    int mySqrt(int x) {
        if(x < 1) return 0; // 处理边界情况
        int left = 1,right = x;
        while(left < right) {
            long long mid = left + (right - left + 1) / 2; // 数据量大，类型改成 long long 更加合适，防溢出
            if(mid * mid <= x) left = mid;
            else right = mid - 1;
        }
        return left;
    }
};

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

020 搜索插入位置

**力扣链接：**69. x 的平方根

题目描述：

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)