First Bad Version

The latest version of a software product fails a quality check. Since each version is built on top of the previous one, every version created after a bad version is also considered bad.

First Bad Version

Problem Statement

The latest version of a software product fails a quality check. Since each version is built on top of the previous one, every version created after a bad version is also considered bad.

You have n versions, numbered [1, 2, ..., n]. You have access to an API function that returns TRUE if the given ID is the ID of a bad version.

Find the first bad version — the one that is causing all the later versions to be bad. The solution should also return the number of API calls made during the process, and should try to keep this number as small as possible.

Constraints

• 1 ≤ first bad version ≤ n ≤ 2³¹ − 1

Examples

Note: The original examples came from an interactive widget and were a bit jumbled in the text. Here they are cleaned up, based on the numbers provided.

Example 1

Input: n = 8

Output: First bad version = 6, API calls made = 3

Example 2

Input: n = 5

Output: First bad version = 3, API calls made = 2

Example 3

Input: n = 7

Output: First bad version = 4, API calls made = 3

Solution

Since this problem needs us to eliminate half of the range at each step, we use the Type 2 binary search method (low < high), rather than the exact-match style of binary search.

Steps

• We set left = 1 and right = n.
• We find the mid point and call isBadVersion(mid):
  • If it returns true, the bad version could be mid itself, or something before it. So we move right to mid — not mid - 1, since mid itself might still be the answer.
  • If it returns false, the bad version must be somewhere after mid. So we move left to mid + 1.
• We repeat this until left and right become equal. At that point, we've found the first bad version.
• We also keep a counter, numOfApiCalls, which increases by 1 every time we check a version. This tracks how many API calls were made in total.

Code

function firstBadVersion(n) {
    let numOfApiCalls = 0,
        left = 1,
        right = n,
        mid = left + Math.floor((right - left) / 2);

    while (left < right) {
        numOfApiCalls++;

        if (isBadVersion(mid)) {
            right = mid;
        } else {
            left = mid + 1;
        }

        mid = left + Math.floor((right - left) / 2);
    }

    return [mid, numOfApiCalls];
}