First Bad Version

最后更新于:2022-04-01 22:58:10

**一. 题目描述** 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. **二. 题目分析** 题目说了一堆,一开始并不知道是想让干什么。后来去网上查了题意,引用如下: 你是一名产品经理,并领导团队开发一个新产品。不幸的是,产品的最终版本没有通过质量检测。由于每一个版本都是基于上一个版本开发的,因此某一个损坏的版本之后的所有版本全都是坏的。 假设有n个版本[1, 2, …, n],现在你需要找出第一个损坏的版本,它导致所有后面的版本都坏掉了。 提供给你一个API `bool isBadVersion(version)`,其功能是返回某一个版本是否损坏。实现一个函数找出第一个损坏的版本。你应该最小化调用API的次数。 原来只需实现类似于[Search for a Range](http://blog.csdn.net/liyuefeilong/article/details/50403616) 的功能,判断坏版本的函数`bool isBadVersion(version)`题目已经提供,无需纠结如何操作,这里还是使用二分查找来解决问题。 **三. 示例代码** 期初使用如下代码一直提示:Time Limit Exceeded ~~~ // Forward declaration of isBadVersion API. bool isBadVersion(int version); class Solution { public: int firstBadVersion(int n) { int low = 1, high = n; int midIndex = 0; while (low <= high) { midIndex = (low + high) / 2; if (isBadVersion(midIndex)) high = midIndex - 1; else low = midIndex + 1; } return low; } }; ~~~ 检查了一段时间,发现当n取很大的数时出现问题,原来是语句`midIndex = (low + high) / 2;` 直接相加时溢出,导致循环超时,该用以下代码Accept。 ~~~ // Forward declaration of isBadVersion API. bool isBadVersion(int version); class Solution { public: int firstBadVersion(int n) { int low = 1, high = n; int midIndex = 0; while (low <= high) { midIndex = low + (high - low) / 2; if (isBadVersion(midIndex)) high = midIndex - 1; else low = midIndex + 1; } return low; } }; ~~~ **四. 小结** 该题的难度在[Search for a Range](http://blog.csdn.net/liyuefeilong/article/details/50403616) 之下,但出现了数据溢出的问题,因此对于简单一些的题也时刻不能掉以轻心啊。
';