69. Sqrt(x) - cocoder39/coco39_LC GitHub Wiki

69. Sqrt(x)

binary search

class Solution:
    def mySqrt(self, x: int) -> int:
        if x == 0 or x == 1:
            return x
        
        low, high = 1, x
        while low + 1 < high:
            mid = low + (high - low) // 2
            if mid > x // mid: # 3 > 8 // 3
                high = mid
            elif mid == x // mid:
                return mid
            else: # mid < x // mid 2 < 8 // 2
                low = mid
        
        if high <= x // high:
            return high
        return low

======================================= corner cases are:

• x = 0, never use 0 to divide other numbers
• at the end, it may happen that start = x / start and end = x / end, return the greater one in this situation, which is end.
• check mid == x / mid instead of mid * mid == x, in case of overflow

int mySqrt(int x) {
        if (x == 0) {
            return 0;
        }
        
        int start = 1, end = x;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (mid < x / mid) {
                start = mid;
            }
            else if (mid > x / mid) {
                end = mid;
            }
            else {
                return mid;
            }
        }
        
        //eg. 2. start == x / start as wll
        //return greater one: end
        if (end == x / end) {
            return end;
        }
        return start;
    }

follow up: 0 < x < 1

int start = x, end = 1, also we can use mid * mid < x, no overflow