Python数据结构与算法51：排序与查找编程练习题2：第一个坏版本

注：本文如涉及到代码，均经过Python 3.7实际运行检验，保证其严谨性。

本文阅读时间约为4分钟。

排序与查找编程练习题2：第一个坏版本

现在有同一个产品的N个版本，编号为从1至N的整数；其中从某个版本之后所有版本均已损坏。现给定一个函数isBadVersion，输入数字N可判断该版本是否损坏（若损坏将输出True）；请找出第一个损坏的版本。

注：有时isBadVersion函数运行速度很慢，请注意优化查找方式。

输入格式:

两行。

第一行为整数，为产品号总数N。

第二行为给定的判断函数，使用有效的Python表达式给出，可使用eval读取。

输出格式：

一行数字，表示第一个损坏的版本。

输入样例：

50
lambda n:n>=30

输出样例：

30

示例代码模板：

N = int(input())
isBadVersion = eval(input())
 
def firstBadVersion(n):
    # code here
    pass
 
print(firstBadVersion(N))

解答：本题有两种查找方法：顺序查找法及二分查找法。顺序查找法比较简单粗暴，直接顺序查找即可，我们用效率更高的二分法来处理。
参考代码如下：

# 排序与查找编程练习题2：第一个坏版本。

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))

To be continued.