Skip to main content

278. First Bad Version

easy

Given n versions where some bad version breaks all later ones, find the first bad version using a minimum number of API calls. The cleanest 'binary-search on a predicate' problem you'll ever see.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

You are a product manager and currently leading a team to develop a new product. Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad. You are given an API bool isBadVersion(version) which returns whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

Constraints

  • 1 <= bad <= n <= 2^31 - 1

Examples

Example 1

Input
n = 5, bad = 4
Output
4

Explanation: call isBadVersion(3) -> false, call isBadVersion(5) -> true, call isBadVersion(4) -> true. Then 4 is the first bad version.

Example 2

Input
n = 1, bad = 1
Output
1

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

The sequence is monotonic: once bad starts, every later version is also bad (FFF...FTTT...T).

Hint 2

Find the leftmost T. That's a textbook lower-bound binary search.

Hint 3

Be careful with overflow on mid = (lo + hi) / 2 when n is near 2^31. Use mid = lo + (hi - lo) / 2.

Solution approach

Reveal approach

Binary search for the leftmost true. Initialize lo = 1 and hi = n. While lo < hi, compute mid = lo + (hi - lo) / 2 (overflow-safe — important since n can be up to 2^31 - 1). If isBadVersion(mid) is true, hi = mid (mid might be the first bad one — keep it in the window). Otherwise lo = mid + 1 (mid and everything left of it is good). When lo == hi, that index is the first bad version. We make O(log n) API calls and use O(1) space. The pattern — binary-search on a boolean predicate with monotonic structure — is the foundation for Koko Eating Bananas, Capacity To Ship Packages, and most binary-search-on-the-answer problems.

Complexity

Time
O(log n)
Space
O(1)

Related patterns

  • binary-search
  • modified-binary-search

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Meta
  • Google
  • Microsoft
  • Amazon

More Binary Search practice problems

See all Binary Search problems →