/* The isBadVersion API is defined in the parent class VersionControl.
boolean isBadVersion(int version); */
// Assuming version number starts with 1
public class Solution extends VersionControl {
public int firstBadVersion(int n) {
int start = 1;
int end = n;
while (start < end){
int mid = start + (end  start)/2;
if (isBadVersion(mid)){
end = mid;
}
else {
start = mid + 1;
}
}
return start;
}
}
SImple binary search solution o(log n)


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/2Here 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 = 1073741825I hope this is helpful! :)