1.题目描述

 

Implement int sqrt(int x).

Compute and return the square root of x.

2.解法分析

很明显，用二分搜索可解，但是需要防止溢出，所以中间结果和上界下界都要用long long 来保存。

class Solution {

public:

int sqrt(int x) {

// Start typing your C/C++ solution below

// DO NOT write int main() function

if(x<0)return -1;

if(x<4)return x>0?1:0;

long long  rmin=0;

long long  rmax=x/2;

long long  rmid;

while(rmin

{

rmid=(rmin+rmax)/2;

if((rmid*rmid)==x)return rmid;

if((rmid*rmid)

else rmax=rmid-1;

}

int result=rmin;

while(result*result>x)result--;

return result;

}

};