[leetcode]First Bad Version

作者:luozhipeng   发表日期:2015-9-19  浏览:2,027次

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.

firstBadVersion

题意:给出一个产品的版本号数组,如有n个版本,则数组为[1, 2, ..., n],如果一个版本在bad版本后开发那么这个版本也是bad版本,已知提供一个判断bad版本的接口isBadVersion(version),求第一个bad版本,并且使调用API的次数最少

 

输入:总版本号n。

返回:第一个bad版本编号k。

 

思路:二分查找即可。

 


class Solution {
public:
    int firstBadVersion(int n) {
        long left = 1, right = n, mid;
        while(left <= right)
        {
            mid = (left + right)>>1;
            if(isBadVersion(mid))
                right = mid -1;
            else
                left = mid + 1;
        }
        return (int)left;
    }
};

 

 

输入:

标签:

本文固定链接: http://www.luozhipeng.com/?p=489
转载请注明: luozhipeng 2015-9-19 于 罗志鹏的BLOG 发表

上一篇: :下一篇
返回顶部