find magic number 这道题值得警惕

经网友提醒，（1）中给出的原解答是错的，因为应对 case [0, 1, 2] 会得出错解答。

正确的应该如下：
int findMagicIndex(int a[], int n) {
    int low = 0, high = n - 1;
    while(low <= high) {
        int mid = (low + high) / 2;
        if (a[mid] >= mid) // 找到一个解之后，继续往左找。
            high = mid - 1;
        else low = mid + 1;
    }

    return low;
}


原理：一旦找到一个解，那么要么左边邻居也是解，要么左边不可能存在解。因为 index i 是连续的，而如果 a[i] 不连续的话，那么一旦错位，就不可能对齐了，所以一个可行解的邻居不是解的话，那么其它地方就不可能有解了。

family2018 发表于 2020-7-13 03:21
即使是第一种情况如果求最小解，楼主考虑过[0,1,2,3,4,5]的binary解法么

是的，这种情况一开始没考虑到，现在已经该成 lower_bound 做法可以得到正确的解了。

关于解（2） 的时间复杂度，最坏情况是 O(N)，但是平均情况肯定是好于 O(N) 的。

那么什么情况会达到 O(N) 呢？ 那就是正好错位1个数的情况。

比如 [1, 2, 3, 4, 5]
i 会不断被置为 a[i]，i 每次只会前进一位。

或者
[-1, 0, 1, 2, 3, 4]
循环每次都只执行 i++，i 每次也只前进一位。

这道题好眼熟，前两天刚做过，但不记得是哪里了，在leetcode上没找到