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;
            }
        }
    }
}

沒有留言: