Why is my binary search implementation slow?


  • 0
    M

    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 b = isBadVersion(mid);
            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;
    }

  • 2
    U

    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.


  • 1

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


  • -1
    S

    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


  • 0

    @LHearen said in Why is my binary search implementation slow?:

    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.


Log in to reply
 

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