每天进步一点点🤏

第一个错误的版本

  • 1003 字

第一个错误的版本

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
你是产品经理,目前正在带领一个团队开发新的产品
不幸的是,你的产品的最新版本没有通过质量检测 由于每个版本都是基于之前的版本开发的,所以错误的版本之后的所有版本都是错的 
假设你有 n 个版本 [1, 2, ..., n],你想找出导致之后所有版本出错的第一个错误的版本 
你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错 实现一个函数来查找第一个错误的版本 你应该尽量减少对调用 API 的次数 

示例 1：
输入：n = 5, bad = 4
输出：4
解释：
调用 isBadVersion(3) -> false 
调用 isBadVersion(5) -> true 
调用 isBadVersion(4) -> true
所以,4 是第一个错误的版本 

示例 2：
输入：n = 1, bad = 1
输出：1

解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
思路:
使用二分法不断压缩范围,判断当前版本为错误,上个版本为正确,是第一个错误的版本

代码:
/**
 * @param Integer $n
 * @return Integer
 */
function firstBadVersion($n) {
    $start = 1;
    $end   = $n;

    // 直到节点重合位置
    while ($start < $end) {
        // 去中间值
        $n = intdiv($end + $start, 2);

        if ($this->isBadVersion($n)) {
            // 中间值错误,则错误的值在$start和$n之间,包含错误的$n
            $end = $n;
        } else {
            // 中间值正确,则错误的值在$n和$end之间,不包含正确的$n
            $start = $n + 1;
        }
    }

    return $end;
}