《010 第一个错误的版本》— 【二分查找】

一、题目

You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.
Suppose you have n versions [1, 2, …, n] and you want to find out the first bad one, which causes all the following ones to be bad.
You are given an API bool isBadVersion(version) which will return whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

Example:
Given n = 5, and version = 4 is the first bad version.
call isBadVersion(3) -> false
call isBadVersion(5) -> true
call isBadVersion(4) -> true
Then 4 is the first bad version.

---

二、分析

【1】线性扫描 (超时)

最直接的方法是进行一次线性扫描，即对 [1…n] 都调用一次 isBadVersion。

public int firstBadVersion(int n) {
  for(int i = 1; i < n; i++) {
    if(isBadVersion(i)) { return i; }
  }
  return n;
}

复杂度分析

时间复杂度：O(n)：在最坏的情况下，最多可能会调用isBadVersion n-1 次.

空间复杂度：O(1)

---

【2】二分查找

二分查找可在在每次操作中减少一半的搜索空间，以此减少时间复杂度。

场景一： 当 isBadVersion(mid) => false

 1 2 3 4 5 6 7 8 9
 G G G G G G B B B 
 |       |       |
left    mid    right

由上可知：mid 左侧（包括自身）的所有版本都是正确的。所以我们令 left=mid+1，把下一次的搜索空间变为 [mid+1,right]。

---

场景二： 当 isBadVersion(mid) => true

 1 2 3 4 5 6 7 8 9
 G G G B B B B B B
 |       |       |
left    mid    right

由上可知知道 mid 右侧（不包括自身）的所有版本的不可能是第一个错误的版本。所以我们令 right=mid，把下一次的搜索空间变为 [left,mid]。

---

public int firstBadVersion(int n) {
  int left = 1, right = n, mid;
  while(left < right) {
    mid = left + (right - left) / 2;
    if(isBadVersion(mid)) { right = mid; }
    else { left = mid + 1; }
  }
  return right;
}

---

需要注意的点：
在二分查找中，选取 mid 的方法一般为 (left+right)。如果使用的编程语言会有整数溢出的情况 (如 C++，Java)，可用 left + (right−left)/2 代替前者。

left+right; //可能会超过 int 而溢出，于是提出了如下办法：
int middle = left + (right - left)/2; //这样防止溢出，等价于：
int middle = left + （right - left） >> 1

---

复杂度分析

时间复杂度：O(logn).

• 二分查找的搜索空间每次减少一半，因此时间复杂度为 O(logn)。

空间复杂度：O(1).

---