How about shrink the search space in the beginning. (real follow-up from interviews)


  • 0
    K
        // idea: instead of binary search on the [1,n] space, 
        // shrink the search space by locating the ending index of search range. This is achieved by continuously expanding length of search range by a factor of 2 until verion at the endind index becomes bad.
        int firstBadVersion(int n) {
            int start = 1, p = 0;
            for(; start + (1LL << p) <= n && !isBadVersion(start + (1LL << p)); p++) {}
            int end = min(1LL*n, start + (1LL << p));
            start = start + (p>0?(1LL << (p-1)) : 0);
            
            while(start < end) {
                int mid = start + (end - start) /2;
                if(!isBadVersion(mid)) start = mid + 1;
                else end = mid;
            }
            return start;
        }
    

  • 0
    M

    Is this supposed to have any advantage? It just looks like a bad idea, making the solution take about twice as long.


  • 0
    K

    @ManuelP said in How about shrink the search space in the beginning. (real follow-up from interviews):

    just looks like a bad idea, making the solution take about twice as long

    This is for follow-up question. It may save a little time when n is very large and 1st bad version is very small.


  • 1
    M

    @Kamikaze_coder Yes, but on average it makes it much slower. And how likely is it that the bug has existed since the early beginning? I'd say not likely. It's more likely that the bug was introduced recently or even in the middle.

    I can imagine the idea being useful on the other end, though. Check n-1, n-2, n-4, n-8, n-16, etc, until you find a good version. And then search after that. Because in reality, the bug was probably introduced recently[*]. If this was indeed an interview question, I suspect this is what the interviewer meant.

    [*] Also, it might be cheaper to test more recent versions than it is to test older versions because rolling the code back to recent versions requires fewer changes (unless you have all versions lying around explicitly)


  • 0
    K

    @ManuelP You are right. I haven't thought about that much details. Thank you.


  • 1
    K

    @Kamikaze_coder After taking @ManuelP 's suggestions, updated the code as below:

        int firstBadVersion(int n) {
            int end = n, p = 0;
            for(; end - (1LL << p) >= 0 && isBadVersion(end - (1LL << p)); p++) {}
            int start = max(0LL, end - (1LL << p));
            end = end - (p>0?(1LL << (p-1)) : 0);
            
            while(start < end) {
                int mid = start + (end - start) /2;
                if(!isBadVersion(mid)) start = mid + 1;
                else end = mid;
            }
            return start;
        }
    

Log in to reply
 

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