LeetCodeDay18 —— 第一个错误的版本

278. 第一个错误的版本

描述

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

说明

• 假设你有 n 个版本 [1, 2, ..., n]，你想找出第一个错误的版本，导致下面所有的错误。
• 你可以通过 bool isBadVersion(version) 的接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。您应该尽量减少对 API 的调用次数。

思路

1. 题目进行了一个包装，本质就是在排序的列表中找到一个数，因此利用二分查找即可。
2. 要注意与二分查找不同的是 end = mid 而不是 mid - 1。每次找到的BadVesion是一个待选版本，不能抛弃。

// Forward declaration of isBadVersion API.
bool isBadVersion(int version);

class Solution_278 {
 public:
  int firstBadVersion(int n) {
    int start = 1, end = n;
    while(start < end){
      int mid = start + (end - start) / 2;
      if(isBadVersion(mid)) end = mid;
      else start = mid + 1;
    }
    return start == end ? start : -1;
  }
};