{x}
blog image

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

Solution Explanation for First Bad Version

This problem involves finding the first bad version in a list of versions using a binary search approach. The isBadVersion(version) API is given, which returns true if the version is bad and false otherwise. We need to minimize the number of calls to this API.

Approach:

The most efficient way to solve this is using binary search. Since all versions after the first bad version are also bad, we can eliminate half of the search space with each comparison.

  1. Initialization: Set left to 1 (the first version) and right to n (the last version).
  2. Iteration: While left is less than right:
    • Calculate the middle index mid using (left + right) // 2 (integer division). Avoid (left + right) / 2 to prevent potential integer overflow issues with large n. Alternatively, left + ((right-left) >> 1) is even safer.
    • Call isBadVersion(mid).
    • If isBadVersion(mid) is true: This means the first bad version is in the left half (including mid). Update right to mid.
    • If isBadVersion(mid) is false: The first bad version is in the right half. Update left to mid + 1.
  3. Return: After the loop, left and right will converge to the first bad version. Return left.

Code Explanation (Python):

class Solution:
    def firstBadVersion(self, n):
        left, right = 1, n
        while left < right:
            mid = left + ((right - left) >> 1)  # safer mid calculation
            if isBadVersion(mid):
                right = mid
            else:
                left = mid + 1
        return left

The Python code directly implements the algorithm described above. The >> 1 is a bitwise right shift, equivalent to dividing by 2. This is a faster way to perform integer division. The left + ((right - left) >> 1) method helps to avoid potential integer overflow errors if left and right are very large numbers.

Time Complexity: O(log n) - Binary search reduces the search space by half in each iteration.

Space Complexity: O(1) - Constant extra space is used. The algorithm operates in-place.

Code in other languages (with minor variations for efficiency and style):

The Java, C++, Go, Rust, and Javascript codes provided all implement the same binary search algorithm, adapting the syntax and data types to each language's conventions. The core logic remains identical to achieve optimal time and space complexity. The minor differences in how mid is calculated are primarily stylistic or for handling potential integer overflow in very large inputs, but all aim for the same efficiency.