给定一个数组 A，如果 某个下标 i, 满足 A[i] = i, 则 i 称为 Magic Index。
现在假设 A 中的元素是递增有序的、且不重复，找出 Magic Index.
更进一步，当数组中有重复的元素呢？？
分析：
首先题目不难。
最简单的当然是 扫描一遍数组，当然这个 O（N）的算法不是最优的。
进一步思考，如今数组是递增的，可否采用 二分搜索，从而加速到 O（lgN）？
if a[mid] == mid, return mid;
if a[mid] < mid, search in range[mid+1, right];
Why? 左半部分一定不会有 Magic index。 反证法： 假如左半部分存在一个 K 是Magic index, 则 a[K] = K.
由于没有重复的元素，所以数组元素从左到右递增的时候，每次增加至少是 1。
从而有 a[mid] > a[K] + mid-K > K + mid - K = mid， 得到矛盾。
if a[mid] > mid, search in range[left, mid-1];
考虑下面的一个例子：
index: 0 1 2 3 4 5 6
value: -10 -5 1 2 4 10 12
a[mid] = 2 < mid = 3, 继续在右半部分找即可，。
二、假设存在重复的元素
由于存在重复的元素，所以数组元素从左到右递增的时候，每次增加不一定大于1了， 有可能是 0。
二分搜索不再使用。每次都必须对 左，右两半都进行搜索。
但是这里还是有一个小 trick,
如果 a[mid] < mid, 左边仅需要搜索 (left, a[mid]), 右边还是搜索 (mid+1, right).
如果 a[mid] > mid, 右边仅需要搜索 (a[mid], right), 左边还是搜索 (left, mid-1).
拿个例子来说明：
index: 0 1 2 3 4 5 6
value: -10 1 1 1 6 10 12
mid = 1 < a[mid] = 3
// copyright @ L.J.SHOU Feb.22, 2014
// magic index
#include <iostream>
using namespace std; // if found, return index;
// if not found, return -1;
int MagicIndex(int A[], int left, int right)
{
int index(-1); if(left <= right)
{
int mid = left + ((right - left) >> 1); if(A[mid] == mid) return mid;
else if(A[mid] < mid){
index = MagicIndex(A, left, A[mid]);
if(index != -1) return index; index = MagicIndex(A, mid+1, right);
if(index != -1) return index;
}
else{
index = MagicIndex(A, left, mid-1);
if(index != -1) return index; index = MagicIndex(A, A[mid], right);
if(index != -1) return index;
}
} return -1;
}