#面试编程题#给定一个数组A，其中有一个位置被称为Magic Index，含义是：如果i是Magic Index，则A[i] = i。假设A中的元素递增有序、且不重复，请给出方法，找到这个Magic Index。当A中允许有重复的元素，该怎么办呢？
第一个，不重复，很简单，用二分查找就OK了。对吧
1 int find_magic_index2(int *list, int count) {
2 int low = 0, high = count - 1;
3 while (high > low) {
4 int idx = (high + low) / 2;
5 if (idx == list[idx])
6 return idx;
7 else if (list[idx] > idx) {
8 high = idx - 1;
9 }
10 else
11 low = idx + 1;
12 }
13
14 return -1;
15 }
第二个，可重复的，该怎么办?从头到尾走一边，总归是可以的嘛。:)。我的想法是，如果a[i]等于i的话，找到了；如果大于i的话，让i=a[i]，不然i++继续找。这样最差的情况才是O(n)
至于为什么可以让i=a[i]，原因由于数列是递增的，所以数组元素在{i, a[i]}的区间中，肯定不可能存在magic index。这样看上去是不是跳跃着前进啊。:)
1 int find_magic_index (int *list, int count) {
2 int i=0;
3 while (i<count) {
4 if (list[i] == i)
5 return i;
6 else if (list[i] > i)
7 i = list[i];
8 else
9 i++;
10 }
11 return -1;
12 }