69. Sqrt(x)

呃，楞做应该不行即使知道 < x/2，二分吧。。

public class Solution 
{
    public int mySqrt(int x) 
    {
        if(x == 0 || x == 1) return x;
        
        int L = 0;
        int R = x/2;
        while(L <= R)
        {
            long M = (long)L + (long)(R - L)/2;
            
            if(M*M > (long)x) R = (int)M - 1;
            else L = (int)M + 1;
        }
        
        if(L * L == x) return L;
        else return L-1;
    
    }
}

注意二分用的是Yes Left No Right。

找到就是Left,找不到就是返还的靠右边的一个，所以要-1...

隐约记得这个题还是另一个可以用牛顿什么法的。。感觉不会考，用前人发现的神奇公式来做这种题有投机取巧的感觉，不过数学这东西本来就是为了“投机取巧”。。。会让我有负罪感。