[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 returns whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

Example 1:

Input: n = 5, bad = 4
Output: 4
Explanation:
call isBadVersion(3) -> false
call isBadVersion(5) -> true
call isBadVersion(4) -> true
Then 4 is the first bad version.

Example 2:

Input: n = 1, bad = 1
Output: 1

Constraints:

• 1 <= bad <= n <= 231 - 1

C code solution:

// The API isBadVersion is defined for you.
// bool isBadVersion(int version);
int firstBadVersion(int n) {
    int lo = 1;
    int hi = n;
    while(lo<hi){
        int mid = lo + ((hi - lo) / 2); //(lo+hi)/2;
        isBadVersion(mid) ? (hi = mid) : (lo = mid + 1);
    }
    return lo;
}

Explanation:

用類似binary search的方式找第一個bad version，每次用lo和hi來界定個範圍，然後查看他們中間的值mid是否為bad version。若否，代表第一個bad version在右側，所以將lo = mid + 1然後進行下一回合，反之則將hi = mid。(lo會多往右一格主要是因為到最後lo, hi兩個一定會在隔壁，所以一定要有某個往前走一步，而選擇是lo往前走而不是hi的原因是當(lo+hi)/2時，是取floor，所以算出來的mid會自動往左靠，因此lo要抵銷這個效應就需要往右走一格)。

要注意overflow!!! 若直接用(lo + hi) / 2來算出mid會發生overflow，因為c code會預設lo和hi原本的data type (這裡是int)來暫存右邊的值，所以當算到lo + hi時就有可能會發生overflow。

解決的方法有兩種:
1. 將lo和hi設成更大的data type，例如unsigned int
2. 利用公式躲避overflow，例如原本為(lo + hi) / 2，改成lo + (hi-lo) / 2