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.

Example:

Given n = 5

call isBadVersion(3) -> false
call isBadVersion(5) -> true
call isBadVersion(4) -> true

Then 4 is the first bad version. 

 

要完成的函数：

bool isBadVersion(int version);

int firstBadVersion(int n) 

 

说明：

1、这道题给定一个函数isBadVersion()，每次输入一个整数，比如调用一下函数isBadVersion(4)，就会知道结果是0/1，也就是4不是/是一个坏版本。

假设你是一个产品经理，需要找出版本序列中第一个坏的版本，比如[0,0,0,1,1]是你调用了上述函数去查找前五次版本评价结果，那么第4个就是第一个坏版本。

此时给你一个整数n，在[1,n]的闭区间中，判断第几个数是第一个坏版本。要求尽量少调用isBadVersion()函数。

保证在[1,n]的闭区间中存在badversion。

2、这道题很明显，就是一道二分查找的题目，查找结束的条件是，上限=下限+1，而这个时候我们返回上限就可以了。

代码如下：（附详解）

    int firstBadVersion(int n) 
    {
        int downlim=1,uplim=n,mid;
        if(isBadVersion(1))//边界条件，如果n==1 或者 n==2并且第一个数是badversion 或者 n>=3并且第一个数就是badversion
            return 1;
        if(n==2)//边界条件，如果n==2并且前面没有成功return，那么必然第2个是badversion
            return 2;
        while(uplim!=(downlim+1))//退出循环的条件
        {
            mid=downlim+(uplim-downlim)/2;//**后面讲解**//
            if(isBadVersion(mid))
                uplim=mid;//不断更新上限
            else
                downlim=mid;//不断更新下限
        }
        return uplim;
    }

标**那里，我们一般情况下都是用mid=(uplim+downlim)/2，但是有些时候这样做会出错，比如uplim和downlim都很大，相加结果会溢出，这时候就不适合这样写了。

我们把它改成mid=dowmlim+(uplim-downlim)/2，同样的结果，这样就不会溢出了。

上述代码实测2ms，beats 100% of cpp submissions。