The most elegant binary search(c 3ms)


  • 2
    T
    int mySqrt(int x) {
        // answer is within [p, q) bound(including p, q not included)
        int p = 0, q=46341;
        while(q-p>1) {
            int mid = (p+q)/2;
            if(mid*mid <= x)
                p = mid;
            else
                q = mid;
        }
        // here [p, p+1), so answer is p
        return p;
    }
    

  • 0

    very neat code!


  • 0
    F

    I am not quite sure whether q = 46341 is a good idea.
    Instead of using multiplication, division can avoid the overflow.

    int mySqrt(int x) {
        int l = 1, r = INT_MAX;
        while (l != r - 1) {
            int m = l + (r - l) / 2;
            if (x / m >= m) l = m;
            else r = m;
        }
        if (x / l >= l) return l;
        return l - 1;
    }
    

  • 0
    J

    Why use q = 46341? Why not q = x? This should save quite a few steps.


  • 0
    F

    @JPBlack
    For int type, the C standard only require that it has at least 16 bits.
    if int is represented as 16 bits, then q = 46341 will result in overflow.
    if int is represented as 64 bits, then q = 46341 is not enough to get the right answer for x = 2147580964 (46342 * 46342).
    q = x will overflow even when int is 32bits.


  • 0
    J

    @FindRX Thank you. I might have to look into C a bit more – I haven't done much with it, yet.


  • 0
    T

    @JPBlack
    I am using sqrt(2^31-1) here. yap, q=x will be faster by few steps. yet the complexity is still constant
    note that q is not included, it is q=x+1, otherwise mySqrt(1) will be wrong.

    @FindRX
    Spec says that BITS(long)>=BITS(int)>=BITS(short)
    I've not seen 64-bit int yet.
    there's some reasons why compilers keeps it 32-bit despite we enter 64-bit world: Portability
    plus int is read as "Integer". generally, 32-bit is big enough.
    in addition, c provide intXX_t.
    I think int will not be enlarged to 64-bit very soon.
    Some old programmers like to store pointer in int, which will cause some problems.
    But nowadays I seldom see one do this. There's intptr_t that define a integer same size as pointer.


Log in to reply
 

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