LeetCode 278 - First Bad Version - Lintcode

http://traceformula.blogspot.com/2015/09/first-bad-version-leetcode.html

You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API bool isBadVersion(version) which will return whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

Example:

Given n = 5, and version = 4 is the first bad version.

call isBadVersion(3) -> false
call isBadVersion(5) -> true
call isBadVersion(4) -> true

Then 4 is the first bad version

X. Classic version:
http://www.bijishequ.com/detail/134759?p=66

Hint: 又是一道二分查找的变种题，**说二分查找是最重要的面试算法真不为过，《编程珠玑》选它作为例子是有道理的。它尤其能考察我们的编码编写和正确性证明能力！**low和high如何增减，low < high还是<=结束等等。

http://www.cnblogs.com/anne-vista/p/4848945.html

    public int firstBadVersion(int n) {
        //use binary search 
        int left = 1;
        int right = n;
        while(left <= right) {
            int mid = left + (right - left) / 2;
            if(!isBadVersion(mid)) {
                left = mid + 1;
            }else {
                right = mid - 1;
            }
        }
        return left;
    }

You are given an API bool isBadVersion(version) which will return whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

This is a typical example of type of binary search that does not return immediately after finding the satisfied element.
Suppose we have 2 pointers start and end. We take middle = (start + end) / 2. Now we check if middle is a bad version. If it is yes, we do not stop here, but we will search on the left, in order to find out that whether there is some smaller bad version. By going to the left, we set end = middle - 1. So if we find nothing on the left, we return end + 1, because it is the last time we saw a bad version. If middle is not a bad version, we simply go to the right by setting start = middle + 1.

One thing to note is that in some programming language, to avoid overflow, we use (end-start)/2 + start instead of (start + end)/2 

1.     public int firstBadVersion(int n) {  
2.         int start = 1;  
3.         int end = n;  
4.         int middle;  
5.         while(start <= end){  
6.             middle = ((end - start)>>1) + start;  
7.             if (isBadVersion(middle)) end = middle - 1;  
8.             else start = middle + 1;  
9.         }  
10.         return end + 1;  
11.     }  

https://leetcode.com/articles/first-bad-version/
 We just need to test an input of size 2. Check if it reduces the search space to a single element (which must be the answer) for both of the scenarios above. If not, your algorithm will never terminate.

public int firstBadVersion(int n) {
    int left = 1;
    int right = n;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (isBadVersion(mid)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

Lintcode: First Bad Version
Also check http://storypku.com/2015/10/leetcode-question-278-first-bad-version/
The code base version is an integer and start from 1 to n. One day, someone commit a bad version in the code case, so it caused itself and the following versions are all failed in the unit tests.

13     public int findFirstBadVersion(int n) {
14         int l = 1;
15         int r = n;
16         while (l <= r) {
17             int m = (l + r) / 2; // use mid = l + (r - l) / 2; to avoid overflow
18             if (VersionControl.isBadVersion(m)) {
19                 r = m - 1;
20             }
21             else {
22                 l = m + 1;
23             }
24         }
25         return l; //
26     }

http://blog.welkinlan.com/2015/05/14/firstbadversion/

    public int findFirstBadVersion(int n) {

        int l = 1, r = n;

        while (l < r) {

            int mid = l + (r - l) / 2;

            if (VersionControl.isBadVersion(mid)) {

                r = mid;

            } else {

                l = mid + 1;

            }

        }

        return VersionControl.isBadVersion(l) ? l : -1;

    }

http://shibaili.blogspot.com/2015/09/day-129-277-find-celebrity.html
This is not efficient - the isBadVersion is called twice in the loop.

class Solution {

public:

    int firstBadVersion(int n) {

        int left = 1, right = n;

        while (left <= right) {

            int mid = left + (right - left) / 2;

            bool bad = isBadVersion(mid);

            if (bad && (mid == 1 || !isBadVersion(mid - 1))) return mid;

            if (bad) {

                right = mid - 1;

            }else {

                left = mid + 1;

            }

        }

         

        return -1;

    }

};

https://leetcode.com/articles/first-bad-version/
Brute force:

public int firstBadVersion(int n) {
    for (int i = 1; i < n; i++) {
        if (isBadVersion(i)) {
            return i;
        }
    }
    return n;
}

Lintcode: First Bad Version

https://github.com/nekocode/leetcode-solutions/blob/master/solutions/278.%20First%20Bad%20Version.md
居然超时了，我自己测了一遍提示超时的 Testcase，但是结果速度很快啊。后来再审了一遍题目，题目要求尽量少调用 isBadVersion() 接口

    public int firstBadVersion(int n) {
        int l = 1, r = n;

        while (true) {
            n = (r - l) / 2 + 1;
            if (n < l) n = l;
            if (n > r) n = r;

            if (isBadVersion(n)) {
                // 如果 n 为 bad version
                if (!isBadVersion(n - 1)) {
                    return n;

                } else {
                    // 前半段继续搜寻
                    r = n - 1;
                }
            } else {
                if (isBadVersion(n + 1)) {
                    return n + 1;

                } else {
                    // 后半段继续搜寻
                    l = n + 1;
                }
            }
        }
    }

http://www.zgljl2012.com/leetcode-278-first-bad-version/
follow up⾮非常谜，问我怎么检查输⼊入是valid，如果输⼊入不不valid怎么返回通
知⽤用户，说了了可以返回error code或者exception，然后让我写抛出
exception
给⼀一个数组⾥里里⾯面是commit number, 分别给good commit 的number和bug
commit的number还提供了了⼀一个boolean isBug(int commitNumber)说这个
function的cost很⼤大