69. Sqrt(x)

int mySqrt(int x) {
        if(x <= 0) return x;  
          
        // Use binary search to find square root  
        int left = 1;  
        int right = x / 2 + 1;  
        int mid = left + (right-left) / 2;  
        while(left +1 < right){  
            mid = left + (right-left) / 2;  
            if(x / mid == mid) return mid;  
            else if(x / mid > mid) left = mid;  
            else right = mid;  
        }
        if(right/mid == mid)
            return right;
        return left;  
    
}