First Bad Version: Predicate search Pattern

Learning Outcome

After this lesson, you should be able to recognize monotonic boolean problems and find the first position where the predicate becomes true.

Problem Statement

You have versions 1 to n. Once a bad version appears, every later version is also bad. Use isBadVersion(version) to return the first bad version.

Brute Force Approach

Check versions from 1 to n and return the first version where isBadVersion is true.

This may call the API O(n) times, which is wasteful when the true/false pattern is monotonic.

Optimized Approach

The search space looks like false, false, false, true, true. Binary search for the first true. If mid is bad, it could be the first bad version, so keep it by moving right = mid. If it is good, move after it.

Exact Pseudocode

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

Reference Code

class Solution:
    def firstBadVersion(self, n):
        left = 1
        right = n

        while left < right:
            mid = left + (right - left) // 2
            if isBadVersion(mid):
                right = mid
            else:
                left = mid + 1

        return left
  

Sample Dry Run

Complexity

Edge Cases

• The first version is bad.
• The last version is the first bad version.
• n = 1.

Interview Checklist

• Describe the monotonic predicate: good then bad.
• Keep mid when it is bad.
• Return the converged boundary.

FAQs

There is no target value. The task is to find the first position where a condition becomes true.

mid may be the first bad version, so we cannot discard it.

Binary search on a monotonic predicate.