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

• 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.

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

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

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

• 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.

• This poster helps me a lot!

• The TLE is because of overflow!

• Thank you for posting this!

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

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

• @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"?

• @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):
"""
:type n: int
:rtype: int
"""
start = 1
end = n
while start < end:
c_v = start +(end-start)>>1
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 ?

• Thanks, make a lot of sense

• 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.

• start+(end-start)/2

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

• 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.

• @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;
}
``````

• @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. :)

• quite a tricky pitfall, thank yo

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