My C code accepted with 5 ms


  • 5
    K
    //binary search
    int mySqrt(int x) {
        if(x == 0)
        {
            return 0;
        }
        int left = 1, right = x;
        int mid = (left + right)/2;
        while(true)
        {
            if(x/mid > mid)
            {
                if((x/mid - mid) == 1)
                {
                    return mid;
                }
                left = mid;
                mid = (left + right)/2;
            }else if(x/mid < mid)
            {
                if((mid - x/mid) == 1)
                {
                    return x/mid;
                }
                right = mid;
                mid = (left + right)/2;
            }else
            {
                return mid;
            }
        }
    }

  • 2
    J

    The algorithm is great, the following is refactor of it, for readability:

    int mySqrt(int x) {
        if (x <= 0) return 0;
        int a = 1;
        int b = (x == INT_MAX) ? (x - 1) : x; // avoid overflow
        while (a < b) {
            if (b - a == 1) return a;
            int m = (a + b) / 2;
            int d = m - (x / m);
            if (d == 0) return m;
            if (d  < 0) a = m;
            else        b = m;
        }
        return a;
    }
    

    Further improvements are welcome!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.