Domain 1EasyCORE

First Bad Version

We are tasked with finding the first bad version in a sequence of versions where all subsequent versions are also bad. The API `isBadVersion(version)` is provided to check if a given version is bad. We need to minimize the number of calls to this API.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Binary Search

278. First Bad Version

Model: qwen2.5-coder:14b
Topics: Binary Search
FAANG asked: 1
Acceptance rate: 37.8%


Problem Breakdown

We are tasked with finding the first bad version in a sequence of versions where all subsequent versions are also bad. The API isBadVersion(version) is provided to check if a given version is bad. We need to minimize the number of calls to this API.

Inputs:

  • An integer n representing the total number of versions.
  • A hidden function isBadVersion(version) that returns True if the version is bad, otherwise False.

Outputs:

  • The first bad version number.

Implicit Constraints or Tricky Edge Cases:

  • If there are no bad versions (which is not possible given the problem constraints), we should return -1.
  • The function should handle large values of n efficiently due to the constraint 1 <= n <= 2^31 - 1.

Intuition

A brute-force approach would involve checking each version from 1 to n sequentially until a bad version is found. This approach has a time complexity of O(n), which is inefficient given the large possible value of n.

The key insight is that since all versions after a bad version are also bad, we can use binary search to minimize the number of API calls. Binary search reduces the problem size by half with each iteration, leading to a much more efficient solution.

Approach

We will use binary search to find the first bad version:

  1. Initialize two pointers, left and right, to 1 and n respectively.
  2. While left is less than or equal to right:
    • Calculate the middle point mid.
    • If isBadVersion(mid) returns True, it means the first bad version is at mid or before mid. So, we move the right pointer to mid - 1.
    • If isBadVersion(mid) returns False, it means the first bad version is after mid. So, we move the left pointer to mid + 1.
  3. When the loop ends, left will be pointing to the first bad version.

Complexity Analysis

  • Time Complexity: O(log n) because we are using binary search to halve the search space in each iteration.
  • Space Complexity: O(1) as we are only using a constant amount of extra space for variables.

Solution

def firstBadVersion(n):
    left, right = 1, n
    while left <= right:
        mid = (left + right) // 2
        if isBadVersion(mid):
            right = mid - 1
        else:
            left = mid + 1
    return left

Edge Cases Handled

  • Single Version: If n is 1, the function will correctly identify it as the first bad version.
  • All Versions Bad: The binary search ensures that we find the first bad version efficiently even if all versions are bad.
  • No Bad Versions (Theoretical): Although not possible in this problem due to constraints, the binary search approach inherently handles cases where no bad version exists by converging on a non-existent bad version.