[leetcode]69. Sqrt(x)

题目链接：https://leetcode.com/problems/sqrtx/#/description

Implement int sqrt(int x).

Compute and return the square root of x.

class Solution { public: int mySqrt(int x) { if(x==0) return 0; int left=1,right=INT32_MAX; while(true) { int mid=left+(right-left)/2; if(mid>x/mid) right=mid-1; else { if(mid+1>x/(mid+1)) return mid; left=mid+1; } } } };

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