LEETCODE，leetcode—sqrt

1.題目描述

?

Implement int sqrt(int x).
?
Compute and return the square root of x.

LEETCODE。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<rmax)

        {

            rmid=(rmin+rmax)/2;

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

            if((rmid*rmid)<x)rmin=rmid+1;

            else rmax=rmid-1;

        }

        int result=rmin;

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

        return result;

    }

};