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.

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.

My solution

bool isBadVersion(int version);

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

直接用O(n)来遍历会超时, 故考虑lgn的方式,自然想到二分.
实际上第一次代码采用二分仍然TLE,将错误示例放到本地debug, 发现原因竟然是越界. 也就是上述代码注释掉的部分. (left + right) / 2 和 left + (right - left) / 2在没有越界发生的时候是等价的(前提是都是正数,简单的理解就是2*left一定是偶数,加在right-left里面一定不会改变其奇偶性,从而不影响/2取整), 而前者涉及大数之间的加法时容易越界!!!!!!

• 虽然总在leetcode优秀代码中看到采用后者的二分方式, 竟然一直忽视!!!
• 另外还有一个经常见到也被自己忽略了的地方,就是for(int i;i<..;i++)还是for(int i;i<..;++i), 运行结果显然是都可以, 但是总有leetcode大神一直写++i,不禁再查一查到底有什么区别. 没看过源码还是太年轻!!

Look : i++和++i 知乎

因为有中间变量, 所以以后等价情况还是用++i效率高

Discuss

也感觉到自己的代码中逻辑不是很清晰, 因为调用isBadVersion有多次.参照网友答案如下:

class Solution {
public:
    int firstBadVersion(int n) {
        int lower = 1, upper = n, mid;
        while(lower < upper) {
            mid = lower + (upper - lower) / 2;
            if(!isBadVersion(mid)) lower = mid + 1;   /* Only one call to API */
            else upper = mid;
        }
        return lower;   /* Because there will alway be a bad version, return lower here */
    }
};

• 我的代码return mid, 因为mid是要经过计算得出的, 所以要初始化, 那初始化为多少呢? 我很尴尬的给了一个n. 看到这个方案中,return lower,不禁感叹自己死脑筋.
• lower=mid+1是不怕越过0的位置的,因为最后return的结果是1存在的位置
• upper=mid而不是mid-1,因为如果这里的mid左边是0, mid-1后从lower到upper全部都是0
• return lower真的很巧妙 = =

Reference

• leetcode 278