NUHMAN.com

Introduction

LeetCode 278: First Bad Version is a textbook example of applying binary search to minimize API calls.

You're given a version control system where one version is known to be “bad,” and every version after it is also bad. Your task is to efficiently identify the first bad version using as few calls as possible to the provided isBadVersion(version) API.

Problem Statement

You are given an integer n, representing the number of versions [1, 2, ..., n]. There is a function isBadVersion(version) that returns whether a version is bad.

Your goal is to find the first bad version, where isBadVersion(version) transitions from False to True.

Example

python

Input: n = 5, bad = 4
Output: 4

Explanation:
isBadVersion(1) → False  
isBadVersion(2) → False  
isBadVersion(3) → False  
isBadVersion(4) → True  
isBadVersion(5) → True  

✅ Step-by-Step Strategy

This is a classic binary search problem:

• Versions are ordered.
• If version v is bad, then all versions v+1 and onward are bad too.
• Once you hit a bad version, go left to find the first bad one.

🔁 Binary Search Logic

1. Set low = 1, high = n
2. While low < high:

• mid = (low + high) // 2
• If isBadVersion(mid):
• Move high = mid (bad version could be earlier)
• Else:
• Move low = mid + 1 (skip the good version)

1. Return low (first version where isBadVersion(low) is True)

✅ Python Code

python

# The isBadVersion API is already defined for you.
# def isBadVersion(version: int) -> bool:

class Solution:
    def firstBadVersion(self, n: int) -> int:
        low, high = 1, n
        while low < high:
            mid = (low + high) // 2
            if isBadVersion(mid):
                high = mid
            else:
                low = mid + 1
        return low

🧪 Dry Run (n = 5, bad = 4)

• low = 1, high = 5
• mid = 3 → not bad → low = 4
• mid = 4 → bad → high = 4
• Exit loop → return 4 ✅

⏱️ Time and Space Complexity

MetricValueTime ComplexityO(log n)Space ComplexityO(1)API Callslog₂(n) max

🔍 Edge Cases

• n = 1, bad = 1 → should return 1
• All versions are bad → should return 1
• Only last version is bad → should return n

✅ Conclusion

LeetCode 278: First Bad Version is a perfect demonstration of:

• Efficient search using binary logic
• Avoiding unnecessary checks
• Reducing API costs in real-world systems (like release pipelines)

It's often used in interviews to assess understanding of search space reduction.