使用交互函数充当 check 进行二分-一一网

这是我参与更文挑战的第 13 天，活动详情查看：更文挑战

题目描述

这是 LeetCode 上的 278. 第一个错误的版本 ，难度为简单。

Tag : 「二分」

你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。

假设你有 n 个版本 [1, 2, ..., n]，你想找出导致之后所有版本出错的第一个错误的版本。

你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。

示例:

给定 n = 5，并且 version = 4 是第一个错误的版本。

调用 isBadVersion(3) -> false
调用 isBadVersion(5) -> true
调用 isBadVersion(4) -> true

所以，4 是第一个错误的版本。 
复制代码

二分

一道交互题，根据题意可知，是尽可能少调用 isBadVersion 方法来找到分割点。

考虑存在「没有错误版本」和「全是错误版本」的情况，但如果往头部插入一个正确版本，往尾部插入一个错误版本作为哨兵，仍然具有「二段性」。

实际上，只需要进行这样的思考即可，不需要真正插入这样的哨兵，把这个哨兵逻辑放到最后返回的时候判断一下即可。

那么只需要将 isBadVersion 当做 check 函数进行二分即可。

二分通常有以下两种写法，分别代表「找到最靠近中心的 True」和「找到最靠近中心的 False」。

另外根据数据范围需要注意计算 mid 时的爆 int 问题，可以通过使用类似 l + (r - l) / 2 的做法解决，也可以通过一个临时 long 来解决。

代码：

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int l = 1, r = n;
        while (l < r) {
            long tmp = (long)l + r >> 1;
            int mid = (int)tmp;
            if (isBadVersion(mid)) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return r;
    }
}
复制代码

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int l = 1, r = n;
        while (l < r) {
            long tmp = (long)l + r + 1 >> 1;
            int mid = (int)tmp;
            if (!isBadVersion(mid)) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }
        return !isBadVersion(r) ? r + 1 : r;
    }
}
复制代码