Magic Index

作者 QIFAN 日期 2016-10-01
Magic Index

A magic index in an array A[1 ... 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?

思路

sorted,find a number,这是不是听起来很熟悉,有一种二分法的冲动?这道题就是可以二分做。

假设数组a是这样:
[-2, 0, 2, 6, 9, 10, 12]

i = 4, a[3] = 6 > 3,可以推断i右边的数组里不可能有magic index,因为数组是递增的。所以用同样的方法到i左边找,直到找到或者找不到。

Base case:

  • a[i] = i,返回true
  • 查找range < 1, 即找不到magic index, 返回false

解题

public boolean isMagic(int[] a) {
if(a == null || a.length == 0 || a[0] > 0) return false;
return isMagic(a, lo, hi);
}
boolean isMagic(int[] a, int lo, int hi) {
int mid = lo + (hi - lo) / 2;
if (int[mid] == mid) return true;
//查找左半边
if (int[mid] > mid) {
return isMagic(a, lo, mid - 1);
}
return isMagic(a, mid + 1, hi);
}

FOLLOW UP

若不是无重复的数组,该怎么做?
只要加一点改进。
假设a[i] = k

  • k > i,至少哪个位置有可能出现magic index? a[k]
  • k < i,哪个位置有可能出现magic index? a[k]

分析

时间复杂度O(logN)
空间复杂度O(1)