278.第一個(gè)錯(cuò)誤的版本
你是產(chǎn)品經(jīng)理塑崖，目前正在帶領(lǐng)一個(gè)團(tuán)隊(duì)開(kāi)發(fā)新的產(chǎn)品。不幸的是痛倚，你的產(chǎn)品的最新版本沒(méi)有通過(guò)質(zhì)量檢測(cè)规婆。由于每個(gè)版本都是基于之前的版本開(kāi)發(fā)的，所以錯(cuò)誤的版本之后的所有版本都是錯(cuò)的蝉稳。
假設(shè)你有 n 個(gè)版本 [1, 2, ..., n]抒蚜，你想找出導(dǎo)致之后所有版本出錯(cuò)的第一個(gè)錯(cuò)誤的版本耘戚。
你可以通過(guò)調(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ò)誤的版本。
來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/first-bad-version
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有廓八。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)奉芦，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處剧蹂。
解題思路1：
暴力解決，直接循環(huán)遍歷判斷宠叼，但是會(huì)超時(shí)。
程序代碼1：
# The isBadVersion API is already defined for you.
# @param version, an integer
# @return a bool
# def isBadVersion(version):
class Solution:
def firstBadVersion(self, n):
"""
:type n: int
:rtype: int
"""
for i in range(1,n+1):
if isBadVersion(i):
return i
s = Solution()
print(s.firstBadVersion())
解題思路2：
還是用經(jīng)典的二分查找來(lái)判斷冒冬。
程序代碼2：
# The isBadVersion API is already defined for you.
# @param version, an integer
# @return a bool
# def isBadVersion(version):
class Solution:
def firstBadVersion(self, n):
"""
:type n: int
:rtype: int
"""
left = 1
right = n
while(left<right):
mid = left + (right - left) // 2
if isBadVersion(mid):
right = mid
else:
left = mid + 1
return left
s = Solution()
print(s.firstBadVersion())
