First Bad Version - Video Solutions

Problem Overview: You are given n product versions labeled from 1 to n. Once a version becomes bad, every version after it is also bad. An API isBadVersion(version) tells whether a version is bad. Your task is to find the first bad version while minimizing the number of API calls.

Approach 1: Binary Search Optimization (O(log n) time, O(1) space)

The versions form a monotonic sequence: once isBadVersion(v) returns true, all versions after v are also true. This pattern fits perfectly with binary search. Start with two pointers left = 1 and right = n. Compute mid and call isBadVersion(mid). If the result is true, the first bad version lies at mid or earlier, so move right = mid. Otherwise the first bad version must be after mid, so move left = mid + 1. Continue until left == right. That index is the first bad version.

This approach works because each API call eliminates half the search space. Instead of checking every version sequentially, the algorithm repeatedly halves the range, reducing the number of checks to log2(n). The implementation is iterative and uses constant extra memory, which is ideal when the number of versions can be extremely large.

The key implementation detail is to avoid skipping the first bad version. When mid is bad, you do not move past it; you keep it in the search range by setting right = mid. This preserves the earliest bad candidate while still shrinking the search window.

Approach 2: Recursive Binary Search Method (O(log n) time, O(log n) space)

This version applies the same binary search logic but uses recursion instead of a loop. Define a recursive function that searches between left and right. Compute mid and call isBadVersion(mid). If mid is bad, recursively search the left half including mid. If it is good, recursively search the right half starting from mid + 1.

The algorithm still performs at most O(log n) API calls because each recursive step halves the remaining range. The difference is space usage. Recursive calls add frames to the call stack, resulting in O(log n) auxiliary space. In practice this approach is easier to reason about but slightly less memory efficient than the iterative version.

The problem itself is categorized as an interactive search task. The main constraint is minimizing API calls rather than raw iteration speed. Recognizing the monotonic pattern and applying divide and conquer through binary search is the critical insight.

Recommended for interviews: Interviewers expect the binary search solution. A linear scan from version 1 to n would take O(n) API calls and quickly becomes infeasible. Showing that you detect the monotonic property and reduce the problem to binary search demonstrates strong algorithmic thinking and familiarity with classic search patterns.