Cracking Coding Interview - 8.3 Magic Index

Magic Index: A magic index in an array A[0...n - 1] is defined to be an index such that A[i] = i. Given a sorted array of distinct integers, write a method to find a magic index, if one exists, in array A.

FOLLOW UP

What if the values are not distinct?

Hints: #170, #204, #240, #286, #340

解法1

看上去就是遍历，和递归没有什么关系。

不过也不是从头到尾都要检查，当发现a[i] > i的时候，就可以不用再找了。这是因为：

• 如果 a[i] > i，考虑到i是整数，那么a[i] >= i + 1。
• 从a是一个不重复的排序数组可知，a[i + 1] > a[i]，同理a[i + 1] >= a[i] + 1。
• 得到a[i + 1] >= i + 1 + 1 >= i + 2 > i + 1
• 因此，因此a[i]之后的所有数字都不可能是a[i] == i。

时间复杂度：O(n)

解法2

比O(n)更小的复杂度是O(logn)和O(1)。提到O(logn)那么就想到二分法，考虑到解法1得到的结论：

• 当a[i] > i的时候就不用再往右边找了

如果a[i] < i能推导出什么呢？

• 考虑到i是整数，可得a[i] <= i - 1
• 因为a[i - 1] < a[i]，可得a[i - 1] <= a[i] - 1
• 可得a[i - 1] <= i - 2
• 因此，a[i]之前的都无法满足a[i] == i

所以当a[i] < i的时候就不用往左边找了，因此我们可以用二分法来找：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

public int findMagicIndex(int[] a, int start, int end) {
  if (start > end) {
    return -1;
  }
  int mid = (start + end) / 2;
  if (a[mid] == mid) {
    return mid;
  }
  if (a[mid] > mid) {
    // 找左边
    return findMagicIndex(a, start, mid - 1);
  }
  // 找右边
  return findMagicIndex(a, mid + 1, end);
}

时间复杂度：O(logn)，n是数组长度

解法3（附加题）

如果存在重复的数字，那么前面的两个推导就要修改了：

如果a[i] > i即a[i] >= i + 1：

• 因为a[i + 1] >= a[i]，所以a[i + 1] >= i + 1
• 也就是说右边还有机会

如果a[i] < i即a[i] <= i - 1：

• 因为a[i - 1] <= a[i]，所以a[i - 1] <= i - 1
• 也就是说左边还有机会

这么看来只能是从头遍历到尾了，时间复杂度O(n)