A good warning to me to use start+(end-start)/2 to avoid overflow


  • 76

    Before this problem, I have always use

      mid = (start+end)) / 2;
    

    To get the middle value, but this can caused OVERFLOW !

    when start and end are all about INT_MAX , then (start+end) of course will be overflow !

    To avoid the problem we can use

      mid =  start+(end-start)/2;
    

    Here is the AC implementation

    // Forward declaration of isBadVersion API.
    bool isBadVersion(int version);

    class Solution {
    public:
        int firstBadVersion(int n) {
            int start=0, end=n;
            cout<<end-start<<end;
            while(end-start>1){
                int mid=start+(end-start)/2;
                /** mid = (start+end)) / 2; **/
                if(isBadVersion(mid))  end=mid;
                else  start=mid;
            }
            return end;
        }
    };

  • 0
    Y

    I think that (start + end) /2 caused Time Limit Exceeded maybe the division operation which dividend is big enough is slow;


  • 1
    L

    nop I think. The compiler will optimize division operation to shift operation.


  • 0
    Y

    I had tried to use shift operation and it got the same result.
    Such a big int takes too much memory to shift I think.


  • 0
    C

    This poster helps me a lot!


  • 0

    The TLE is because of overflow!


  • 0
    C

    Thank you for posting this!


  • 0
    S

    @YeFlush NOP.the following code will be accept(even though it is cheating).

    int mid = ((long)start + end) / 2;


  • 0
    S

    @RainbowSecret
    hi
    could you please explain it for me why you used "start=mid" for else condition?

    I mean I know if mid is bad version, then end=mid,
    but when mid is not bad version, how can you choose which way to move?
    why it should be "start=mid" instead of "end=mid"?


  • 0
    D

    @YeFlush
    I solved it with Python.But ' (start+end)/2 ' is faster than ' start+(end-start)/2 ' ! Why ?
    Here is the code of method ' start+(start-end)/2 ':

    class Solution(object):
        def firstBadVersion(self, n):
            """
            :type n: int
            :rtype: int
            """
            start = 1
            end = n
            while start < end:
                c_v = start +(end-start)>>1
                if isBadVersion(c_v) is True:
                    end = c_v
                else :
                    start = c_v+1
            return start
    

    But when I change c_v = start+(end-start)>>1 to c_v=(end+start)>>1, it even faster ! Why ?


  • 0
    H

    Thanks, make a lot of sense


  • 0
    W

    Overflow happens because sums greater than 2^31-1 but less than 2^32-1 will be negative. For example, if you added 1 to 2^31-1, you'd get int32.minvalue, or -2^31. Lets use a smaller example, say an 8bit number, the max signed value you can store is 01111111, which is 127. If you add one, what do you expect to get as a result? It should be 10000000, which is -128. Due to this overflow, your code will likely infinitely loop.

    In C# there's a compiler flag (checked) that will throw an exception for overflow/underflow, but the default behavior is the same as java/c++ with "wrapping" or modulo 2^bitcount of your number type.

    In case that didn't make sense or you want to learn more, refer to this article to learn more about exactly what number your sum is becoming: http://www.cplusplus.com/articles/DE18T05o/


  • 0
    H

    said in A good warning to me to use start+(end-start)/2 to avoid overflow:

    start+(end-start)/2

    Thank you so much! I've been stuck here for 30 mins


  • 0

    Can anyone explain why do I have to do return isBadVersion(start) ? start : end; at the end if I start with start = 1 instead of start = 0? Thank you.


  • 0
    E

    @tony.mu101999 I believe the return value also depends on your while condition. Please see my code, hope it can help

    public int firstBadVersion(int n) {
            int start = 1, end = n;
            while(end >= start) {
                int mid = start + (end - start)/2;
                if (isBadVersion(mid)) end = mid - 1;
                else start = mid + 1;
            }
            return start;
        }
    

  • 0
    A

    @RainbowSecret Ha, I just found I used (start+end)/2 but didn't get overflow. Why? Because I always use uint when I know negative is not possible. This really saves me from a lot of boundary conditions. :)


  • 0
    H

    quite a tricky pitfall, thank yo


Log in to reply
 

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