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

019 x 的平方根

题目描述： 计算并返回 x 的平方根，其中 x 是非负整数。由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

1.1 思路一：暴力解法

1.1.1 算法思路

依次枚举 [0, x] 之间的所有数（这里没有必要研究是否枚举到 x/2 还是 x/2 + 1。因为我们找到结果之后直接就返回了，往后的情况就不会判断。反而研究枚举区间，既耽误时间，又可能出错）：

（1）如果 i * i == x，直接返回； （2）如果 i * i > x，说明之前的一个数是结果，返回 i - 1。

由于 i * i 可能超过 int 的最大值，因此使用 long long 类型。

1.1.2 算法实现

class Solution {
public:
    int mySqrt(int x) {
        // 由于两个较大的数相乘可能会超过 int 最大范围
        // 因此用 long long
        long long i = 0;
        for (i = 0; i <= x; i++) {
            // 如果两个数相乘正好等于 x，直接返回 i
            if (i * i == x) return i;
            // 如果第一次出现两个数相乘大于 x，说明结果是前一个数
            if (i * i > x) return i - 1;
        }
        // 为了处理 oj 题需要控制所有路径都有返回值
        return -1;
    }
};

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

1.2 思路二：二分查找

1.2.1 算法思路

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

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

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

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

1.2.2 算法实现

class Solution {
public:
      {
        (x < )  ; 
         left = , right = x;
        (left < right) {
              mid = left + (right - left + ) / ; 
            (mid * mid <= x) left = mid;
             right = mid - ;
        }
         left;
    }
};