导航
导航
文章目录
  1. 题目
  2. 翻译

LeetCode-278.First Bad Version

题目

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.

翻译

你是一个产品经理,目前正在领导一个小组开发一个新产品。不幸的是,最新版本的产品没有通过质量测试。因为每个版本都是基于前一个版本开发的,一个坏版本之后的所有版本都是坏的。
假设你有n个版本 [1, 2, …, n] ,并且你想要找到导致后面坏版本的第一个坏版本。
你可以使用一个API bool isBadVersion(version) ,可以判断某个 version 是否是坏版本。实现函数,找到第一个坏版本。你应当最小化API的调用次数。

本题可理解为有重复元素的有序数组,寻找下界。
设立左右指针,每次取中,判断是否坏版本。如果mid是坏版本,则更新right为mid,否则更新left为mid+1。直到左右同时指向第一个坏版本停止。
需要注意一点,在取中时不能直接加除以2,可能出现溢出情况:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/* The isBadVersion API is defined in the parent class VersionControl.
boolean isBadVersion(int version); */

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

参考:
http://blog.csdn.net/xudli/article/details/48286081