LeetCode 0278. First Bad Version第一個(gè)錯(cuò)誤的版本【Easy】【Python】【二分】
Problem
You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.
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 will return whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.
Example:
Given n = 5, and version = 4 is the first bad version.
call isBadVersion(3) -> false
call isBadVersion(5) -> true
call isBadVersion(4) -> true
Then 4 is the first bad version.
問題
你是產(chǎn)品經(jīng)理斥废，目前正在帶領(lǐng)一個(gè)團(tuán)隊(duì)開發(fā)新的產(chǎn)品。不幸的是，你的產(chǎn)品的最新版本沒有通過質(zhì)量檢測(cè)成艘。由于每個(gè)版本都是基于之前的版本開發(fā)的讹弯，所以錯(cuò)誤的版本之后的所有版本都是錯(cuò)的土浸。
假設(shè)你有 n 個(gè)版本 [1, 2, ..., n]昼弟，你想找出導(dǎo)致之后所有版本出錯(cuò)的第一個(gè)錯(cuò)誤的版本。
你可以通過調(diào)用 bool isBadVersion(version) 接口來(lái)判斷版本號(hào) version 是否在單元測(cè)試中出錯(cuò)普办。實(shí)現(xiàn)一個(gè)函數(shù)來(lái)查找第一個(gè)錯(cuò)誤的版本工扎。你應(yīng)該盡量減少對(duì)調(diào)用 API 的次數(shù)。
示例:
給定 n = 5衔蹲，并且 version = 4 是第一個(gè)錯(cuò)誤的版本肢娘。
調(diào)用 isBadVersion(3) -> false
調(diào)用 isBadVersion(5) -> true
調(diào)用 isBadVersion(4) -> true
所以，4 是第一個(gè)錯(cuò)誤的版本舆驶。
思路
二分查找
因?yàn)榘姹臼菑?1 到 n橱健，所以 low 初值設(shè)為 1，high 初值設(shè)為 n沙廉。
時(shí)間復(fù)雜度: O(logn)
空間復(fù)雜度: O(1)
Python代碼
# The isBadVersion API is already defined for you.
# @param version, an integer
# @return a bool
# def isBadVersion(version):
class Solution(object):
def firstBadVersion(self, n):
"""
:type n: int
:rtype: int
"""
low, high = 1, n # 1-n
while low <= high:
mid = int((low + high) / 2)
if isBadVersion(mid) == False:
low = mid + 1
else:
high = mid - 1
return low
