LeetCode : 69. Sqrt(x)

[congr]

https://leetcode.com/problems/sqrtx/

[congr]

class Solution {
    public int mySqrt(int x) {
        if (x == 0) return 0;

        int low = 1, high = x/2+1;
        while (low+1 < high) {
            int mid = (low + high) / 2;
            int target = x / mid;

            if (target > mid) low = mid;
            else if (target < mid) high = mid;
            else return mid;
        }

        return low;
    }
}