Untitled

class Solution {
    public int mySqrt(int x) {
        if(x==1){
            return 1;
        }
        int ans=0;
        int low=1;
        int high=x/2;
        while(low<=high){
            int mid=(low+high)/2;
            long sqrt=((mid%1000000007)*(mid%1000000007))%1000000007;
            if(sqrt==x){
                return mid;
            }else if(sqrt>x){
                high=mid-1;
            }else{
                low=mid+1;
                ans=mid;
            }
        }
        return ans;
    }
}