海文考研培训班2023价格表优化网络推广外包

二分查找

• 思路：
  • 设置 left 指针为 0，right 指针为 x；
  • 如果 mid = (right - left) / 2 + left 的平方小于或等于 x，此时移动 left = mid + 1，并缓存当前 mid 值，可能这个 mid 就是结果，或者 x 的平方根有更大的数；
  • 否则移动 right 到 mid -1，因为 mid^2 > x，x 的平方根比 mid 小；
  • 直到找到 mid 的值；

class Solution {
public:int mySqrt(int x) {int left = 0;int right = x;int result = -1;while (left <= right) {int mid = (right - left) / 2 + left;if ((long long) mid * mid <= x) {result = mid;left = mid + 1;} else {right = mid - 1;}}return result;}
};