First Bad Version

First Bad Version

1. What is this problem about?

The First Bad Version interview question is a classic search optimization problem. You are a product manager and have $n$ versions of a product. Once a version is "bad," all subsequent versions are also bad. You are given an API isBadVersion(version) and need to find the first bad version while minimizing the number of API calls.

2. Why is this asked in interviews?

This is one of the most common questions at Google, Microsoft, and Amazon. It tests your fundamental understanding of Binary Search. It evaluations if you can recognize that a linear search ($O(N)$) is sub-optimal for a monotonic property (a sequence of False values followed by True values). It's the "Hello World" of Binary Search interview patterns.

3. Algorithmic pattern used

This problem follows the Binary Search on a Monotonic Property pattern.

1. Range: left = 1, right = n.
2. Logic:
   • Calculate mid = left + (right - left) / 2.
   • If isBadVersion(mid) is true, then mid could be the first bad version, or the first bad version is to the left. Move right = mid.
   • If isBadVersion(mid) is false, all versions up to mid are good. Move left = mid + 1.
3. Result: When left == right, you have found the first bad version.

4. Example explanation

$n = 5$, First bad version is 4.

1. left=1, right=5, mid=3. isBad(3) is false. left = 4.
2. left=4, right=5, mid=4. isBad(4) is true. right = 4.
3. left == right. Result: 4.

5. Common mistakes candidates make

• Integer Overflow: Using (left + right) / 2 which can exceed the integer limit for large $n$. Always use left + (right - left) / 2.
• Termination Condition: Using left <= right and right = mid - 1, which requires more complex logic to return the correct boundary. The left < right and right = mid approach is usually cleaner for finding the first occurrence.
• Linear Search: Suggesting a loop from 1 to $n$, which is $O(N)$ and fails the efficiency requirement.

6. Interview preparation tip

Binary Search is the standard solution for finding a "transition point" in any sorted or monotonic space. Practice identifying the "property" that allows you to discard half the search space.