Java Binary Search Solution


  • 0
    M
    public int mySqrt(int x) {
            if(x <= 0) {
                return x;
            }
            
            int ret = 1;
            while(ret < x/ret) {
                ret = 2*ret;
            }
            
            if(ret == x/ret) {
                return ret;
            }
            
            int start = ret/2, end = ret;
            while(start <= end) {
                int mid = start + (end - start)/2;
                if(mid == x/mid) {
                    return mid;
                } else if (mid < x/mid) {
                    ret = mid;
                    start = mid + 1;
                } else {
                    end = mid - 1;
                }
            }
            return ret;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.