0278. First Bad Version
=======================
题目信息
--------
:题号: 0278
:难度: Easy
:主题: 有序版本、单调布尔接口、边界查找
:原题: `LeetCode 0278 `_
:重点: 版本编号从 1 开始、坏版本一旦出现后续全部为坏、返回最早的坏版本并减少接口调用
题目重述
--------
产品共有 ``n`` 个按发布时间排列的版本,编号为 ``1`` 到 ``n``。其中某个版本是第一个坏版本,从它开始的所有后续版本也都是坏版本。平台提供 ``isBadVersion(version)`` 接口,用于查询指定版本是否为坏版本;实现函数并返回第一个坏版本的编号。
题目保证 ``1 <= firstBad <= n <= 2^31 - 1``,因此至少存在一个坏版本。只能通过给定接口判断版本状态,不能直接访问隐藏的首个坏版本值。应尽量减少对 ``isBadVersion`` 的调用次数,返回值使用一基版本编号。
自建示例
--------
坏版本位于后半段:
.. code-block:: text
输入:n = 8,isBadVersion(1..5) = false,isBadVersion(6..8) = true
输出:6
解释:版本 6 是第一个返回 true 的版本,版本 1 到 5 都是好版本。
只有一个版本:
.. code-block:: text
输入:n = 1,isBadVersion(1) = true
输出:1
解释:题目保证至少有一个坏版本,因此唯一版本就是第一个坏版本。
寻找第一个 true
----------------
把 ``isBadVersion`` 看成单调布尔序列:好版本为 ``false``,从首个坏版本开始全部为 ``true``。
在闭区间 ``[left,right]`` 内二分:
* ``mid`` 为坏版本时,首个坏版本不晚于 ``mid``,保留左半边并令 ``right=mid``;
* ``mid`` 为好版本时,首个坏版本一定在右侧,令 ``left=mid+1``。
循环结束时 ``left==right``,这个位置仍在候选区间内且是首个坏版本。中点计算使用
``left + (right-left)/2``,避免两个一基大编号相加时溢出。
正确性说明
----------
循环不变量是:首个坏版本位于 ``[left,right]``。坏中点不能被排除,因为它自己可能是首个;
好中点及其左侧都不可能是首个,只能排除。区间长度每轮严格减小,终止时唯一候选就是首个坏版本。
C++ 实现
--------
.. code-block:: cpp
// The judge provides isBadVersion(int version).
class Solution {
public:
int firstBadVersion(int n) {
long long left = 1;
long long right = n;
while (left < right) {
const long long middle = left + (right - left) / 2;
if (isBadVersion(static_cast(middle))) {
right = middle;
} else {
left = middle + 1;
}
}
return static_cast(left);
}
};
代码分析
--------
每轮只调用一次接口并把候选区间缩小约一半,接口调用次数和时间复杂度为 ``O(log n)``,
额外空间为 ``O(1)``。使用 ``long long`` 保存边界,避免在 ``n`` 接近 ``2^31-1`` 时中点表达式溢出;
题目保证至少存在一个坏版本,所以不需要处理“全为好版本”的额外返回值。