First Bad Version

首先，今天的文章发的很晚了，十分抱歉，（没关系，反正也没有读者。。。）

今天还是一道较为容易的题目：First Bad Version

该题是LeetCode中Difficulty为Easy的题目，Acceptance为20.0%。

题目如下：

---

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.
Credits:Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.

题目的难度不大，可以采用O(n)的算法，当然最好的算法还是O(logn)的算法，即采用Binary Search的方法，具体代码如下：

首先的Java版：

---

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

接下来是C++版：

---

    class Solution {
    public:
    int firstBadVersion(int n) {
        int lower = 1, upper = n, mid;
        while(lower < upper) {
            mid = lower + (upper - lower) / 2;
            if(!isBadVersion(mid)) lower = mid + 1; 
            else upper = mid;
        }
        return lower; 
      }
    } 

以上代码均来自LeetCode的discuss，感谢这些算法的贡献者。