【C++算法】20.二分查找算法_x 的平方根

---

题目链接：

69. x 的平方根

---

题目描述：

---

解法

暴力解法：

如果x=17

从1，2，3，4，5......这些数里面找他们的平方，16<x<25，所以整数部分是4

二段性：

可以使用二分查找

需要注意：0 <= x <= 2³¹ - 1

也就意味着x是可以比1小的，但这个时候直接就是0了。

---

C++ 算法代码：

暴力查找

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

二分查找

class Solution 
{public:int mySqrt(int x) {if(x < 1) return 0; // 处理边界情况int left = 1, right = x; //从1-x二分while(left < right){long long mid = left + (right - left + 1) / 2;if(mid * mid <= x) left = mid;else right = mid - 1;}return left;}
};

---

图解

例如：x=8

1. left=1，right=8

   进入循环，mid=1+(8-1+1)/2=1+4=5

2. left=1，right=4

   进入循环，mid=1+(4-1+1)/2=1+2=3

   right = mid - 1=2

3. left=1，right=2

   进入循环，mid=1+(2-1+1)/2=1+1=2

   mid * mid <= x，left = mid=2

4. left=2，right=2，不满足循环条件，return left;返回2。