本文共 944 字，大约阅读时间需要 3 分钟。

class Solution {//using binary search to solve sqrt(x)//alternative method: newton methodpublic:	int sqrt(int x) {		// Start typing your C/C++ solution below		// DO NOT write int main() function		if(x <= 1) return x;		int l = 0; 		int r = x;		while (l <= r)		{			int m = l+(r-l)/2;			int now = x/m;//avoid overflow			if (now < m)				r = m-1;			else if(now > m)				l = m+1;			else return m;		}		return r;//the small one is the answer	}};

second time

class Solution {public:    int sqrt(int x) {        // Start typing your C/C++ solution below        // DO NOT write int main() function        long long left = 0;        long long right = x;        while(left <= right)        {            long long mid = left+(right-left)/2;            long long square = mid*mid;//... maybe out of range            if(square < x) left = mid+1;            else if(square > x) right = mid-1;            else return mid;        }        return (int)right;    }};

转载地址：http://mqxti.baihongyu.com/