L69 Sqrt(x)

Binary Search

Problem

Implement int sqrt(int x).

Compute and return the square root of x, where x is guaranteed to be a non-negative integer. (开方）

Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.

Example 1:

Input: 4 Output: 2

Example 2:

Input: 8 Output: 2 Explanation: The square root of 8 is 2.82842..., and since the decimal part is truncated, 2 is returned.

Solution

• target becomes x/mid

• if mid is too larger, right = mid;

• too small, left= mid;

public int mySquare(int x){
    if(x < 0) return -1;
    if(x < 1) return 0;
    if(x < 4) return 1;
    
    int left = 1, right = Integer.MAX_VALUE;
    while(left + 1 < right){
        int mid = left + (right - left) /2;
        if(mid == (x / mid)) return mid;
        else if(x > (x / mid)) right = mid;
        else left = mid;
    }
    if(right < (x / right)) return right;
    return left;
}