LeetCode-278. First Bad Version

本文主要是介绍LeetCode-278. First Bad Version，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

问题：https://leetcode.com/problems/first-bad-version/?tab=Description
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.
你是一个产品经理，目前正在带领团队去开发一个新产品。不幸的是，产品的上一个版本没有通过质量检测。因为每个版本都是建立在前一个版本基础上开发的，所以坏版本之后的版本也都是坏的。假设你有n个版本[1,2,…,n]，并且你想找出造成后面所有版本都变坏的第一个坏版本。
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.
给你一个API——bool isBadVersion(version)，它能够确定一个版本是否是坏的。实现一个函数去找出第一个坏版本。你应该尽可能少地去调用这个API。
分析：二分查找的问题。假设用1代表Bad Version，0代表Good Version，你有n个版本，所以这n个版本的质量好坏一定是这样的[0……01……1]，现在要找出第一个1的位置，所以先判断中间位置的版本的好坏，如果为1，则在左边查找，如果为0，则在右边查找。然后继续查找左半边或右半边的中间位置的版本好坏。
C++代码：

// Forward declaration of isBadVersion API.
bool isBadVersion(int version);class Solution {
public:int firstBadVersion(int n) {int l=0;int r=n;while(l<=r){int mid=l+(r-l)/2;if(isBadVersion(mid)){r=mid-1;}else{l=mid+1;}}return l;}
};