# Leetcode 69. Sqrt(x) (C語言)
- 題目
Implement int sqrt(int x).
Compute and return the square root of x, where x is guaranteed to be a non-negative integer.
Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.
- 範例
Input: 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since
the decimal part is truncated, 2 is returned.

int mySqrt(int x){
	if(x==0)return 0;
	if(x==1)return 1;
    double l=0,r=x,temp;
    while((int)r-(int)l!=0){
        temp=(r+l)/2;
        if(temp*temp>x){
            r=temp;            
        }
        else if(temp*temp<x){
            l=temp;           
        }
        else{
            return temp;
        }
    }
    return (int)temp;
}

思路:Binary search 分成l,temp,r三部分,如果temp^2>x就代表temp右邊平方皆>x都可捨棄，反之亦然

0               x/2                  x
l---------------temp-----------------r

if(x/2)^2>x

0               x/2                  x
l---------------temp                 r

if(x/2)^2<x
0               x/2                  x
l               temp-----------------r

逐漸逼近，且此題不看小數，只要整數部分即可，故終止條件只要l,r整數部分相同就可停止回傳整數部分。