原題
代碼庫(kù)的版本號(hào)是從 1 到 n 的整數(shù)博肋。某一天，有人提交了錯(cuò)誤版本的代碼蜂厅，因此造成自身及之后版本的代碼在單元測(cè)試中均出錯(cuò)匪凡。請(qǐng)找出第一個(gè)錯(cuò)誤的版本號(hào)。
你可以通過(guò) isBadVersion 的接口來(lái)判斷版本號(hào) version 是否在單元測(cè)試中出錯(cuò)掘猿，具體接口詳情和調(diào)用方法請(qǐng)見(jiàn)代碼的注釋部分病游。
給出 n=5
調(diào)用isBadVersion(3)，得到false
調(diào)用isBadVersion(5)稠通，得到true
調(diào)用isBadVersion(4)衬衬，得到true
此時(shí)我們可以斷定4是第一個(gè)錯(cuò)誤的版本號(hào)
解題思路
- 相當(dāng)于找第一個(gè)target元素，例如找第一個(gè)1
00000001111111111111111
完整代碼
# 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
"""
start, end = 0, n
while start + 1 < end:
mid = start + (end - start) / 2
if isBadVersion(mid):
end = mid
else:
start = mid
if isBadVersion(start):
return start
else:
return end
