题目大意：
第一个错误的版本
你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。
假设你有 n 个版本 [1, 2, …, n]，你想找出导致之后所有版本出错的第一个错误的版本。
你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。
示例:
给定 n = 5，并且 version = 4 是第一个错误的版本。 调用 isBadVersion(3) -> false 调用 isBadVersion(5) -> true 调用 isBadVersion(4) -> true 所以，4 是第一个错误的版本。
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=278
解题思路分析：
我们最终要求的答案实际上是正确与错误版本的分界线，这非常类似于在一个递增数组中找特定值，对于这类问题，二分查找是最好的方案。初始时，二分的low位于1，high位于n。mid是他们的中间值。如果版本mid是错误版本，那么说明mid之后都是错误版本，我们将范围缩小至low到mid-1范围，反之范围扩大至mid+1到high范围，重复此过程，直到low大于high为止，最终的low即是答案。
这是一道典型而简单的二分查找题目。如果你对二分查找不熟悉，或者你很苦于二分查找的边界问题，建议你参考我之前总结的文章：LEETCODE常见算法之二分查找超详细白话讲解
另外本题还有一个需要注意的地方，由于n会非常大，在计算low+high时可能会超出int范围，因此需要将low与high定义为long型。
实现代码：
public int firstBadVersion(int n) {
long low=1,high=n;
while(low<=high){
int mid=(int)((low+high)/2);
if(isBadVersion(mid)){
high=mid-1;
}else{
low=mid+1;
}
}
return (int)low;
}本题解法执行时间为12ms。
Runtime: 12 ms, faster than 98.79% of Java online submissions for First Bad Version.
Memory Usage: 36.1 MB, less than 5.63% of Java online submissions for First Bad Version.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-278-first-bad-version解题思路分析/