西瓜是肥貓

題目長這個樣子

Implement int sqrt(int x).

Compute and return the square root of x.

就是要實作尋找最接近無條件捨去的平方根整數。

以下是我的答案，使用二分搜尋法去尋找平方根。

二分搜尋法我就不重述一次網路上有太多高手解說過了 

這邊就放一個我查到的某個解說的連結吧：http://openhome.cc/Gossip/AlgorithmGossip/BinarySearch.htm

這題呢，我是使用JavaScript去做以下是我的答案：

/**
 * @param {number} x
 * @return {number}
 */
var mySqrt = function(x) {
    if(x==0) return 0;
    left = 1, right = Number.MAX_SAFE_INTEGER;
    while (true) {
        mid = left + (right - left)/2;
        if (mid > x/mid) {
            right = mid - 1;
        } else {
            if (mid + 1 > x/(mid + 1))
                return mid;
            left = mid + 1;
        }
    }
};