69. Sqrt(x)

注意 range 是 1 ~ x, 要找平方根

left ~ right: 1~x

finally, return right

A little trick is using i <= x / i for comparison, 
instead of i * i <= x, to avoid exceeding integer upper limit.

Binary Search Solution: 

Time complexity = O(lg(x)) = O(32)= O(1)  (log(2^32) = 32)

space: O(1)

    public int mySqrt(int x) {
        int left = 1; //1~x
        int right = x;

        while (left <= right) {
            int mid = left + (right - left) / 2; // (left + right) >>> 1

            if (mid == x / mid) { // 4 8/4=2
                return mid;
            } else if (mid < x / mid) {
                left = mid + 1;
            } else {
                right = mid - 1; //3
            }

        }

        return right; // in the end, right must < left, so ans is right
    }

另一種思路

https://leetcode-cn.com/problems/sqrtx/solution/er-fen-cha-zhao-niu-dun-fa-python-dai-ma-by-liweiw/

class Solution {
    public int mySqrt(int x) {
        
        int left = 0;
        int right = x;
        
        while (left < right) {
            int mid = (left + right + 1) >>> 1; //取右中位數
            
            // we want to select mid*mid <= x
            // so use mid > x/mid in if
            if (mid > x/mid) {  
                right = mid - 1;
            } else {
                left = mid;
            }
        }
        return left;
    }
}

new style

use x/mid, 但要注意 edge case (0,1)

```java
class Solution {
    public int mySqrt(int x) {
        if (x == 0 || x == 1) { // avoid edge case, divide by 0, and 1...
            return x;
        }

        int left = 0;
        int right = x;

        int bound = 0;
        while (left <= right) {
            int mid = left + (right - left)/2;
            int current = x/mid;
            if (mid == current) {
                return (int)mid;
            } else if (mid < current) { // 在範圍內, 取值
                bound = Math.max(bound, mid);
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return bound;
    }
}
```

use 乘法, 但要 long, 不然會溢位

class Solution {
    public int mySqrt(int x) {
        long left = 0;
        long right = x;

        long bound = 0;
        while (left <= right) {
            long mid = left + (right - left)/2;
        
            long current = mid*mid;
            if (current == x) {
                return (int)mid;
            } else if (current < x) { // 在範圍內, 取結果
                bound = Math.max(bound, mid);
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return (int)bound;
    }
}