給定一個數組 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

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

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;
}