LeetCode OJ: 69. Sqrt(x) 平方根

題目連結，此題當然可以用程式語言內建的數學函式sqrt解題，只不過這樣子就沒意思啦，在Wiki上可查到很多數學解法，其中牛頓法是個不錯的選擇，不過改完的結果比較像Binary Search耶。

public class Solution {
    public int mySqrt(int x) {
        if (x == 0)
            return 0;

        int left = 1, right = Integer.MAX_VALUE;
        
        while (true) {
            int mid = left + (right - left)/2;
            
            if (mid > x/mid) {
                right = mid - 1;
            } else {
                if (mid + 1 > x/(mid + 1))
                    return mid;
                left = mid + 1;
            }
        }
    }
}

若您覺得文章寫得不錯，請點選文章上的廣告，來支持小編，謝謝。