Solution: First Bad Version

Statement

The latest version of a software product has failed the quality check. Because each version builds on the previous one, all versions developed after a bad version are also considered bad. You are given n versions identified by integers $[1, 2,3, \dots, n]$, and an API function isBadVersion(version) that returns TRUE if a given version is bad.

Your task is to find the first bad version that causes all subsequent versions to fail while minimizing the number of API calls.

Constraints:

• $1 \leq$ first bad version $\leq$ n

Solution

So far, you’ve probably brainstormed some approaches and know how to solve this problem. Let’s explore some of these approaches and determine which one to follow based on considerations such as time complexity and implementation constraints.

Naive approach

The naive approach is to find the first bad version in the versions range by linear search. We traverse the whole version range one element at a time until we find the target version.

The time complexity of this approach is $O(n)$ because we may have to search the entire range in this process. This approach ignores important information: the range of version numbers is sorted from $1$ to $n$. Let’s see if we can use this information to design a faster solution.

Optimized approach using modified binary search

In this solution we use binary search to check the middle version to determine if it is bad.

• If the middle version is good, the first bad version must be later in the range, so the first half of the range is skipped.

• If the middle version is bad, we focus on the first half of the range to find the first bad version, allowing us to skip the second half.

We repeat the process after identifying which half of the range to search. For the identified half, we check the middle version again to decide whether to search the first or second half of the current range. This process continues until the first bad version is found.

Binary search is the most suitable approach for finding the first bad version because the versions are sorted from $1$ to n. It executes in $O(\log{n})$ time, which is faster than the alternate linear scanning method.

Here’s the step-by-step implementation of the solution:

1. Initialize first = 1 and last = n to define the search range.

2. While first <= last, perform the following steps:

   1. Calculate mid = first + (last - first) / 2 to find the middle value.

   2. If isBadVersion(mid) is TRUE:

      1. Set last = mid - 1 because the first bad version is present in the left half of the versions.

   3. Otherwise:

      1. Set first = mid + 1 because the first bad version is present in the right half of the versions.

3. Return first, which now represents the first bad version.

Let’s look at the following illustration to get a better understanding of the solution: