[LeetCode] Sqrt(x)

Problem:

Implement int sqrt(int x).

Compute and return the square root of x.

Solution:O(logn)

public class Solution {
    public int sqrt(int x) {
        long left = 0;
        long right = (1<<16)-1;
        long mid = 0;
        while(left<=right){
            mid = (left+right)/2;
            if(mid*mid > (long)x){
                right = mid;
            }
            else if((mid+1)*(mid+1) > (long)x){
                break;
            }else{
                left = mid;
            }
        }
            return (int)mid;
    }
}

Key Concept: Use binary way to get the answer