First Bad Version is the problem that separates candidates who’ve memorized binary search from those who actually understand it. You’re not searching an array — you’re searching a conceptual space using a predicate. The candidates who struggle aren’t missing the pattern; they’re getting tripped up by whether to use hi = mid or hi = mid - 1, and that single decision determines whether their code works or loops forever.

---

The Problem

You have n versions [1, 2, ..., n]. After some version, all subsequent versions are bad. Given an API isBadVersion(version) which returns True if the version is bad, find the first bad version. Minimize the number of API calls.

Example

Input: n = 5, bad = 4 API calls: isBadVersion(3) → false, isBadVersion(4) → true Output: 4

Already comfortable with the solution? Practice it in a mock interview →

---

What Interviewers Are Actually Testing

Skill	What Interviewers Observe
Binary search on a condition	Do you recognize this as a boolean monotonic search?
Invariant maintenance	Do you keep the answer within [lo, hi] at all times?
Overflow handling	Do you use lo + (hi - lo) // 2 instead of (lo + hi) // 2?
Off-by-one elimination	Do you know when to use hi = mid vs hi = mid - 1?

---

Step 1: Clarifying Questions

1. Is the first version always potentially bad? Yes — bad could be 1.
2. What if all versions are good? The problem guarantees at least one bad version exists.
3. Is isBadVersion expensive? Yes — we must minimize calls. This is why binary search, not linear scan.

---

Step 2: The Naive Idea

Linear scan from 1 to n, return the first version where isBadVersion is true. O(n) API calls — correct but does not minimize calls.

---

Step 3: The Key Insight

The versions form a monotonic boolean sequence: all False, then all True. Binary search finds the first True in O(log n) by eliminating half the search space at each step. When isBadVersion(mid) is True, the answer is at or before mid. When False, the answer is strictly after mid.

---

Step 4: Optimal Strategy

1. Set lo = 1, hi = n.
2. While lo < hi:
   • Compute mid = lo + (hi - lo) // 2.
   • If isBadVersion(mid) is True: hi = mid (answer could be mid or earlier).
   • If False: lo = mid + 1 (answer must be after mid).
3. Return lo.

---

Python Implementation

def firstBadVersion(n: int) -> int:
    lo, hi = 1, n

    while lo < hi:
        mid = lo + (hi - lo) // 2  # Overflow-safe midpoint
        if isBadVersion(mid):
            hi = mid      # mid could be the answer; keep it in range
        else:
            lo = mid + 1  # mid is good; answer is strictly after

    return lo  # lo == hi: the only candidate remaining

---

Time & Space Complexity

Aspect	Complexity
Time	O(log n)
Space	O(1)
API calls	O(log n)

---

Common Interview Mistakes

1. Integer overflow with (lo + hi) // 2. In Python this isn’t a practical issue (arbitrary precision integers), but interviewers still expect you to use lo + (hi - lo) // 2 — it shows awareness and is critical in other languages.

2. Using hi = mid - 1 when isBadVersion(mid) is True. This excludes mid from consideration, but mid could be the first bad version. Must use hi = mid.

3. Off-by-one in the exit condition. Using lo <= hi requires an explicit return inside the loop. The lo < hi variant terminates cleanly with lo == hi pointing to the answer.

4. Not explaining why minimizing API calls matters. The interviewer wants to hear “binary search finds the answer in O(log n) calls vs. O(n) for linear scan.”

---

What a Strong Candidate Sounds Like

“The key observation is that versions form a monotonic sequence — all good versions come before all bad versions. Binary search is perfect for finding the boundary. I’ll maintain lo and hi as my search range, always keeping the first bad version within [lo, hi]. When mid is bad, I narrow to [lo, mid]. When mid is good, I narrow to [mid+1, hi]. When lo and hi converge, that’s my answer. O(log n) API calls.”

---

Example Interview Dialogue

Interviewer: Why hi = mid and not hi = mid - 1?

Candidate: Because when isBadVersion(mid) returns True, mid itself could be the first bad version. If I set hi = mid - 1, I’d exclude a potential answer. By keeping hi = mid, the answer always stays within my search range.

Interviewer: Would this still work in Java or C++?

Candidate: The algorithm is the same. The only difference is that in Java or C++, (lo + hi) could overflow a 32-bit integer, so the lo + (hi - lo) / 2 form is essential there.

---

Related Problems to Practice

• Binary Search — The foundation. Master the standard template first.
• Search in Rotated Sorted Array — Binary search with a twist: the array is rotated.
• Search Insert Position — Same lower-bound binary search pattern.

---

Practice This in a Mock Interview

The difference between getting First Bad Version right and wrong comes down to one decision: hi = mid vs hi = mid - 1. That decision feels obvious when reading about it. Under interview pressure, candidates second-guess themselves. Practice until the invariant reasoning is automatic.

Start a mock interview for First Bad Version on Intervu.

---

Further reading:

• How to Prepare for a Coding Interview in 2026, the complete roadmap
• Why LeetCode alone isn’t enough, and what to practice instead
• Practice any LeetCode problem as a live mock interview
• The Grind 75 Pathway, a structured study plan with AI practice links
• Browse all walkthroughs on GitHub