First Bad Version
@resleet I think we are assuming there is at least a good and a bad version in the array so N is at least 2.
quite a tricky pitfall, thank yo
This link has a pretty good explanation of what @Samuel-Song mentioned about integer overflow.
@zilan (start + end) can overflow the int range and it will give a garbage value which will be divided by 2. start + (end - start)/2 does not let that happen. Keeps everything in the int range.
@lee215 How about a 1-liner using reduce?
my ugly binary search solution :)
Can you please expand on those "detail"?
Do you know the difference between (b-a)/2 + a and (b+a)/2 ? Why this will cause stackoverflow?
You solution is based on there must exist bad version. if all versions are not bad, your solution won't work. Example, n is 1 and 1 is good version.
No one has replied
Did you check if your loop might become infinite loop in some cases?
I get it, thanks
Because your ( Start + end ) value can go beyond Integer.MAX_VALUE and hence giving you a negative value.
Eg : start = 1073741824 , end = 1073741827
if mid = (start + end) /2 the mid = 2147483651/2
Here the numerator is more than the integer range in java. hence making mid = -2147483644/2 = -1073741822 which is wrong
if mid = start + (end - start)/2 then
mid = 1073741824 + 1 = 1073741825
I hope this is helpful! :)
I think it is my experience that tells me to do so ... When we add two INT32, we should always be careful for the overflow.
Very nice to update res in the loop! You don't really need to use long, simply use int and write mid as mid = start + ((end-start)>>1); would work.
Disabled Categories are greyed out
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.