Python數據結構與算法51：排序與查找編程練習題2：第一個壞版本

注：本文如涉及到代碼，均經過Python 3.7實際運行檢驗，保證其嚴謹性。

本文閱讀時間約為4分鐘。

排序與查找編程練習題2：第一個壞版本

現在有同一個產品的N個版本，編號為從1至N的整數；其中從某個版本之後所有版本均已損壞。現給定一個函數isBadVersion，輸入數字N可判斷該版本是否損壞（若損壞將輸出True）；請找出第一個損壞的版本。

注：有時isBadVersion函數運行速度很慢，請注意優化查找方式。

輸入格式:

兩行。

第一行為整數，為產品號總數N。

第二行為給定的判斷函數，使用有效的Python表達式給出，可使用eval讀取。

輸出格式：

一行數字，表示第一個損壞的版本。

輸入樣例：

<code>
50
lambda
 
n:n>=30 

/<code>

輸出樣例：

<code>
30
/<code>

示例代碼模板：

<code>N = int(input())
isBadVersion = eval(input())
 
def
 
firstBadVersion
(n)
:

     
    
pass
 
print(firstBadVersion(N))
/<code>

解答：本題有兩種查找方法：順序查找法及順序查找法。順序查找法比較簡單粗暴，直接順序查找即可，我們用效率更高的二分法來處理。 參考代碼如下：

<code> 

N
 = 
int(input())
isBadVersion
 = 
eval(input())

def
 
firstBadVersion(n):
    
low
 = 
1 

    
high
 = 
n
    
while
 
low <= high:
        
mid
 = 
(low + high) // 2  # 設立中值。                
        
if
 
isBadVersion(mid):
            
high
 = 
mid - 1
        
else
:

            
low
 = 
mid + 1
    
return
 
low

print(firstBadVersion(N))
/<code>

To be continued.