题目描述
你是产品经理,目前正在带领一个团队开发新的产品。不幸的是,你的产品的最新版本没有通过质量检测。
由于每个版本都是基于之前的版本开发的,所以错误的版本之后的所有版本都是错的.
假设你有 n 个版本 [1, 2, …, n],你想找出导致之后所有版本出错的第一个错误的版本。
你可以通过调用 bool isBadVersion(version)
接口来判断版本号 version 是否在单元测试中出错。
实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。
示例:
1 | 给定 n = 5,并且 version = 4 是第一个错误的版本。 |
题目分析
简单的二分搜索. 每次找区间[from, to]中间的元素查看是否为badVersion, 如果是, 则查找[from, (to - from) / 2], 否则查找[(to - from) / 2 + 1, to], 直到from == to 或者 from == to - 1, 此时判断如果isBadVersion(from) == isBadVersion(to)
则返回from, 否则返回to.
源码(简单)
1 | bool isBadVersion(int version); |
进阶问题
如果isBadVersion()
函数只会返回当前位的状态, 并不知道状态true和false哪一个是错误的, 这种情况下要怎么解决呢?
源码(进阶)
1 | bool isBadVersion(int version); |