tsanmmmm2000's Tech Blog

Question

Implement int sqrt(int x).

Compute and return the square root of x.

Thinking

題目為求平方根，解法有很多，第一種我們可以用Binary Search，不過要注意可能隱藏的兩個Overflow陷阱

1. 在計算mid時，low + high很可能會超過int的最大值，因此我們需要稍微改變寫法，推導如下：\(mid = {low + high\over 2} = low + {1\over2}(high-low)\)
2. 在推算x平方根時，我們不能以x < mid * mid或x > mid * mid的方式來判斷，因為mid * mid亦可能會超過int最大值，應以mid = x / mid的原則下去運算

另一個要注意的是回傳值得是high，原因在於題目是求整數，而我們要找出一個小於或等於x平方根的最大整數

1. 當mid最後是落在mid < x / mid區間時，因為mid = high此時小於x的平方根，已符合條件，直接回傳high即可
2. 當mid最後是落在mid > x / mid區間時，因為mid = high此時大於x的平方根，而high必須得減1才能符合小於或等於的條件，因此執行high = mid - 1後，最後也是回傳high即可

第二種，我們可以使用牛頓法(Newton's Method)。求x的平方根我們可以用函數\(f(a) = a^2-x=0\)來表示，而我們求其導數\(f'(a)=2a\)，依據牛頓法的迭代公式\(a_{n+1} = a_n-{f(a_n) \over f'(a_n)}\)，我們就可以推算出\(a_{n+1}=a_n-{a_n^2-x \over 2a_n} = {a_n\over2}+{x\over2a_n}={1\over2}(a_n+{x\over a_n})\)，這樣就變簡潔多了

My C# Solution

public class Solution {
    public int MySqrt(int x) {
        if (x == 0) return x;
        var low = 1;
        var high = x;
        int mid;
        while(low <= high)
        {
            mid = low + (high - low) / 2;
            if (mid > x / mid)
            {
                high = mid - 1;
            }
            else if (mid < x / mid)
            {
                low = mid + 1;
            }
            else
            {
                return mid; 
            }
        }
        return high;
    }
}

public class Solution {
    public int MySqrt(int x) {
        if (x == 0) return x;
        long result = x;
        while (result > x / result)
        {
            result = (result + (x / result)) / 2;
        }
        return Convert.ToInt32(result);
    }
}

Reference：Integer square root - Wikipedia、Newton's method - Wikipedia、Newton Iterative Sqrt Method