Leetcode-Java/leetcode/solution/src/FirstBadVersion.java at master · WeilunZ/Leetcode-Java · GitHub

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
29
30
31
32
33
34
35
36
37
38
39
/**
 * https://leetcode.com/articles/first-bad-version/
 */
public abstract class FirstBadVersion {

    public int firstBadVersion(int n) {
        int left = 1, right = n;

        while (left < right) {
            int mid = left + ((right - left) >>> 1);

            if (isBadVersion(mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        return left;
    }

    public int firstBadVersion2(int n) {
        int left = 1, right = n;

        while (left <= right) {
            int mid = left + ((right - left) >> 1);

            if (isBadVersion(mid)) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        return left;
    }

    abstract boolean isBadVersion(int version);
}