# Why is my binary search implementation slow?

• I have two solutions for this problem. Both are essentially modified binary search algorithms. Why is my second implementation slower than the first one. I was expecting the second to converge in lesser number of iterations and hence faster!

Implementation 1: 18-19ms

``````public int firstBadVersion(int n) {
int lo = 1;
int hi = n;
while(lo < hi){
int mid = lo + (hi - lo)/2;
if(!isBadVersion(mid)) lo = mid + 1;
else hi = mid;
}
return hi;
}
``````

Implementation 2: 44-45ms

``````public int firstBadVersion(int n) {
int hi = n;
int lo = 1;
while(lo < hi){
int mid = lo + (hi - lo)/2;
boolean a = isBadVersion(mid - 1);
boolean c = isBadVersion(mid + 1);
if(!a && b) return mid;
if(!b && c) return mid + 1;
if(!a && !b && !c) lo = mid + 1;
if(a && b && c) hi = mid - 1;
}
return hi;
}``````

• Because the api calls are much heavier than the iterations in this problem, you should reduce api calls as much as possible and then reduce the number of iterations.

• @mishrasonu1993 @uriel888 has shed some light on it, besides the more you're doing in the binary searching loop, the more you are turning it into a linear searching and you did lots of other checking too.

• Correct version of your code

``````public int firstBadVersion(int n) {
int lo = 0;
int hi = n-1;
while(lo < hi){
int mid = lo + (hi - lo)/2;
if(!isBadVersion(mid)) lo = mid + 1;
else hi = mid-1;
}

return lo;
}
``````

This should work

• besides the more you're doing in the binary searching loop, the more you are turning it into a linear searching and you did lots of other checking too.

Upvote for `besides the more you're doing in the binary searching loop, the more you are turning it into a linear searching and you did lots of other checking too.`

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