# 【LeetCode】 278. First Bad Version

## Description
> 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.

> 你是一個PM且現在正在領導一個小組去開發一個新的產品。不幸地，你們產品的最新版本沒有通過品質確認。因為每個版本都是基於前一個版本開發，因此所有失敗版本後的版本也都是失敗的。

> 假設你有`n`個版本`[1, 2, ..., n]`且你想找出第一個失敗的版本，因為它造成後面每一個都失敗。

> 你有一個API `bool isBadVersion(version)` 可以回傳版本是否失敗。實作一個函式可以找到第一個失敗的版本。你應該最小化呼叫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. 

## Solution

* 目標是找出API從`false`變成`true`的瞬間，除非第一個版本就是錯誤版本。
* 尋找的方法使用二分搜尋法，每次都檢查中間點是否為切換點：
* 如果是切換點(`isBadVersion(mid) != isBadVersion(mid + 1)`)，回傳中間點。
* 如果在切換點後(都是`true`)，往前面找。
* 如果在切換點前(都是`false`)，往後面找。

### Code

// The API isBadVersion is defined for you.
// bool isBadVersion(int version);

class Solution {
public:
    int find(int s, int e)
    {
        double temp = (double)s + (double)e;
        int mid = temp / 2;
        if(isBadVersion(mid) != isBadVersion(mid + 1))
            return mid + 1;
        else if(isBadVersion(mid) == false)
            return find(s, mid);
        else
            return find(mid, e);
    }
    int firstBadVersion(int n) {
        if(isBadVersion(1)) return 1;
        return find(n, 1);
    }
};

###### tags: `LeetCode` `C++`