携手创造，共同成长！这是我参与「日新方案 8 月更文应战」的第29天，点击查看活动概况

标题

假设你是产品司理，现在正在带领一个团队开发新的产品。不幸的是，你的产品的最新版别没有经过质量检测。由于每个版别都是根据之前的版别开发的，所以过错的版别之后的一切版别都是错的。

假设你有 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$ 和 $n$，其中 $n$ 是给定的版别数量。设定左右鸿沟之后，每次咱们都根据左右鸿沟找到其中间的版别，查看其是否为正确版别。如果该版别为正确版别，那么第一个过错的版别必定坐落该版别的右侧，咱们缩紧左鸿沟；不然第一个过错的版别必定坐落该版别及该版别的左侧，咱们缩紧右鸿沟。

这样咱们每判别一次都能够缩紧一次鸿沟，而每次缩紧时两鸿沟间隔将变为原来的一半，因此咱们至多只需要缩紧 $O(\log n)$ 次。

代码

class Solution : VersionControl {
    func firstBadVersion(_ n: Int) -> Int {
        var left: Int = 1
        var right: Int = n
        while left < right {
            let min = left + (right - left) / 2
            if isBadVersion(min) {
                right = min
            } else {
                left = min + 1
            }
        }
        return left
    }
}

复杂度剖析

• 时刻复杂度：$O(\log n)$，其中 $n$ 是给定版别的数量。

• 空间复杂度：$O(1)$。咱们只需要常数的空间保存若干变量。