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

题目描述

这是 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;
    }
}
复制代码

• 时间复杂度：O(\log{n})O(logn)
• 空间复杂度：O(1)O(1)

其他「二分」相关题解

• 二分模板 29. 两数相除 : 二分 + 倍增乘法解法（含模板）
  
• 二分本质 & 恢复二段性处理
  33. 搜索旋转排序数组（找目标值） : 严格 O(logN)，一起看清二分的本质
  81. 搜索旋转排序数组 II（找目标值） : 详解为何元素相同会导致 O(n)，一起看清二分的本质
  153. 寻找旋转排序数组中的最小值（找最小值） : 严格 O(logN)，一起看清二分的本质
  154. 寻找旋转排序数组中的最小值 II（找最小值） : 详解为何元素相同会导致 O(n)，一起看清二分的本质
  
• 二分 check 函数如何确定 34. 在排序数组中查找元素的第一个和最后一个位置 : 考察对「二分」的理解，以及 check 函数的「大于 小于」怎么写
  

最后

这是我们「刷穿 LeetCode」系列文章的第 No.278 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先将所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。