LeetCode #278: First Bad Version
β’ 190 words β’ 1 min β’ updated
LeetCode #278: First Bad Version:
python
# The isBadVersion API is already defined for you.
# def isBadVersion(version: int) -> bool:
class Solution:
def firstBadVersion(self, n: int) -> int:
# both inclusive
p = 1
q = n
last = None
while p < q:
m = p + (q - p) // 2 # m = (p + q) // 2
if not isBadVersion(m):
p = m + 1
else:
last = m
q = m
if isBadVersion(p):
return p
return last
# a b c d
# p m q
# a b c
# p m qBeware of off-by-one errors.
Simpler:
python
# The isBadVersion API is already defined for you.
# def isBadVersion(version: int) -> bool:
class Solution:
def firstBadVersion(self, n: int) -> int:
# both inclusive
p = 1
q = n
while p < q:
m = p + (q - p) // 2 # m = (p + q) // 2
if not isBadVersion(m):
p = m + 1
else:
q = m
return p
# a b c d
# p m q
# a b c
# p m q