First Bad Version

Find the first version that broke everything using binary search.

binary-search search array

You are given a list of versions represented by booleans in order from oldest to newest. Each version is either good (False) or bad (True). Once a version becomes bad, all subsequent versions are bad (the list is a prefix of good versions followed by all bad versions). Write a function `find_first_bad(is_bad)` that returns the index (0-based) of the first bad version, or -1 if there is no bad version. The list is passed as a list of booleans.

You must implement the function `find_first_bad(is_bad: list) -> int`. Your solution should run in O(log n) time, where n is the length of the list. You may assume the input list is valid (all good then all bad).

Constraints

1 <= len(is_bad) <= 10^5
Input list consists only of booleans.
The list is guaranteed to be a prefix of False (good) followed by True (bad).

Example

>>> find_first_bad([False, False, True, True])
2
>>> find_first_bad([True, True, True])
0
>>> find_first_bad([False, False, False])
-1
>>> find_first_bad([])
-1

10 points ~15 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Think about the boundary between False and True.

If the middle element is True, the first bad is at or before mid.

If the middle element is False, the first bad is after mid.

Keep track of the leftmost True you have seen.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.