First Bad Version DSA Solution - Predicate Search - Study Chapter | QuizMaker

First Bad Version explained with brute force, predicate binary search, dry run, edge cases, complexity, and Python, C++, Java code.

Read: 9m
Type: Chapter
Access: Free

Course

DSA Course: Interview Patterns and Problem Solving

Topic

Module 3: Binary Search

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.

Input	Hidden bad version	Output
`n = 5`	`4`	`4`

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

class Solution {
public:
    int firstBadVersion(int n) {
        int left = 1;
        int right = n;

        while (left < right) {
            int mid = left + (right - left) / 2;
            if (isBadVersion(mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        return left;
    }
};

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int left = 1;
        int right = n;

        while (left < right) {
            int mid = left + (right - left) / 2;
            if (isBadVersion(mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        return left;
    }
}

Sample Dry Run

left	right	mid	isBadVersion(mid)	Action
1	5	3	false	Move left to 4
4	5	4	true	Move right to 4
4	4	-	-	Return 4

Complexity

Measure	Value	Reason
Time	O(log n)	Each API call halves the version range.
Space	O(1)	Only boundaries are stored.

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

Why not use equality search?

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

Why move right = mid when bad?

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

What is the core pattern?

Binary search on a monotonic predicate.