Space
Open
From Fieldwork
Scales
Archive
This is binary search, but on a monotone predicate instead of searching for a target value.
Define a boolean function:
P(v) = isBadVersion(v)
Given the problem statement, P(v) looks like:
False, False, False, True, True, True ...
So we want the first index where P(v) becomes True.
That corresponds to “bisect_left over a boolean array where False < True”:
bisect_left([F,F,F,T,T], True) -> index of first True
class Solution:
def firstBadVersion(self, n: int) -> int:
left, right = 1, n # invariant: answer is in [left, right]
while left < right:
mid = left + (right - left) // 2
if isBadVersion(mid):
# mid is bad, so the first bad is at mid or to the left
right = mid
else:
# mid is good, so the first bad must be to the right
left = mid + 1
return leftPractice bench
A private scratchpad for this reading. Nothing is sent or scored.
What is still unclear, or what would change the explanation?
Saved on this device · one draft per mode