Square Root of Integer

Implement int sqrt(int x).

Compute and return the square root of x.

If x is not a perfect square, return floor(sqrt(x))

Input : 11
Output : 3

DO NOT USE SQRT FUNCTION FROM STANDARD LIBRARY

思路：

we want to find largest y such that y * y <= x. We can do a binary search on the range 0 ~ IntMax, if we find y * y = x, return y. Otherwise we return right pointer.
Because at the end of the search, right pointer points to the smaller int that we want.
For example, we want to find sqrt(10)
in the first round, mid = 3, mid * mid = 9, so we set left = mid + 1 = 4.
Second round, mid = (4 + 5) / 2 = 4, mid * mid = 16 > 10. so we set right = mid - 1 = 3, and the loop ends.
And we see that right will point us to the lower bound that we want.
      r  l
1 2 3 4 5

Solution:

Time : O(32) => O(1)
Space: O(1)

public class Solution {
    public int sqrt(int a) {
        int left = 0;
        int right = Integer.MAX_VALUE;
        long expected = a;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            long power = (long) mid * mid;
            if (power == a) {
                return mid;
            } else if (power > expected) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return right;
    }
}