ChunNote
0%

leetCode-278:First Bad Version

发表于 分类于

问题描述

给定一个正整数 n，表示有 n 个版本，版本是连续的，从其中某个版本开始后面的版本都是有问题的，可以通过调用函数 bool isBadVersion(version) 来判断版本是好的还是坏的，要求尽量少的调用此函数，找出第一个坏的版本。题目链接：点我

样例输入输出

输入：n = 5, bad = 4

输出：4

解释：

调用 isBadVersion(3) -> false
调用 isBadVersion(5) -> true
调用 isBadVersion(4) -> true
所以 4 是第一个坏的版本

输入：n = 1, bad = 1

输出：1

问题解法

此题要求尽量少的调用 isBadVersion 函数，因此不能直接从头开始一个个查找，因为有特性 ”从某个版本坏了之后后面的版本都是坏的“，因此可以使用二分查找快速缩小范围，找到第一个坏的版本。代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/* The isBadVersion API is defined in the parent class VersionControl.
      boolean isBadVersion(int version); */

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int begin = 1;
        int end = n;
        while (begin <= end) {
            int mid = begin + (end - begin) / 2;
            if (isBadVersion(mid)) {
                end = mid - 1;
            } else {
                begin = mid + 1;
            }
        }
        
        if (isBadVersion(end)) {
            return end;
        }
        
        return end + 1;
    }
}