int mySqrt(int x) {
    int left = 0;
    int right = x/2+1;
    long long root = 0;

    while(left<=right) {
        root = (left+right)/2;
        if(root*root < x) left = root+1;
        else if(root*root > x) right = root-1;
        else return root;
    }

    return right;
}