278 - First bad version

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

中文題解

假設您有 n 個版本 [1, 2, ..., n] 並且您想找出第一個壞掉的版本，因爲這導致之後所有版本都是壞的。

題目給予了一個 API bool isBadVersion(version) 能夠返回該版本是否錯誤。

思路

設A爲正常運作的版本，B爲壞掉的版本，得到以下的陣列，因爲B一定在A後面（有正常版本之後才會有壞掉，且題目假設第一個壞掉之後所有版本都是壞的），我們可以以二元搜尋法來迭代陣列並逐漸收窄搜尋範圍來提升效率。

left = 1
right = 6
mid = (1 + 6) // 2 = 3
result = 6  # 預設值：最後版本必然爲壞掉的

 1  2  3  4  5  6
[A, A, A, B, B, B]
 l     m        r

isBadVersion(3) -> false # 將 left 指到 mid + 1
left = 3 + 1 = 4
right = 6
mid = (4 + 6) // 2 = 5
result = 6

 1  2  3  4  5  6
[A, A, A, B, B, B]
          l  m  r

isBadVersion(5) -> true # result = 5, right = mid - 1
left = 4
right = 5 - 1 = 4
mid = (4 + 4) // 2 = 4
result = 5

 1  2  3  4  5  6
[A, A, A, B, B, B]
          l
                    r
                    m

isBadVersion(4) -> true # result = 4, right = mid - 1
left = 4
right = 4 - 1 = 3 # left > right, 結束迴圈

 1  2  3  4  5  6
[A, A, A, B, B, B]
          l
             r  m

完整程式碼

/**
 * The knows API is defined in the parent class Relation.
 * isBadVersion(version: number): boolean {
 *     ...
 * };
 */

var solution = function(isBadVersion: any) {

    return function(n: number): number {
        let l = 0, r = n
        let badVersion = n
        
        while (l <= r) {
            const mid = Math.floor((l + r) / 2)
            if (isBadVersion(mid)) {
                r = mid - 1
                badVersion = mid
            } else {
                l = mid + 1
            }
        }
        
        return badVersion
    };
};