careercup-遞歸和動态規劃 9.3

9.3 在數組A[0...n-1]中，有所謂的魔術索引，滿足條件A[i]=i。給定一個有序整數數組，元素值給不相同，編寫一個方法，在數組A中找出一個魔術索引，若存在的話。

進階：

如果數組元素有重複值，又該如何處理。？

解法一，選擇蠻力法，我們可以直接疊代通路整個數組，找出符号條件的元素。

解法二：既然給的數組是有序的，我們理應充分利用這個條件。

你看你會發現這個問題與經典的二分查找問題非常相似。充分運用比對法，就能找到适當的算法，我們又該怎樣運用二分查找法呢？

在二分查找中，要找出元素k，我們會先拿它跟數組中間的元素x比較，确定k位于x的左邊還是右邊。

以此為基礎，是否通過檢查中間元素就能确定魔術索引的位置？

通過比較A[mid]<mid，可以确定該魔術索引一定在mid的右邊，是以left=mid+1;

如果A[mid]>mid，可以取得該魔術索引一定在mid 的左邊，是以right=mid-1；

算法如下：

如果存在重複元素，前面的算法就會失效。以下面的數組為例：

-10 -5 2 2 2 3 4 7 9 12 13

  0   1  2 3 4 5 6 7 8 9 10 11

看到A[mid]<mid時，我們無法判定魔術索引位于數組哪一邊。它可能在數組右側，跟前面一樣。或者，也可能在左側（在本例中的确在左側）。

它有沒有可能在左側的任意位置呢？不可能。由A[5]=3可知，A[4]不可能是魔術索引。A[4]必須等于4,其索引才能成為魔術索引，但數組是有序的，故A[4]必定小于A[5]。

事實上，看到A[5]=3時按照前面的做法，我們需要遞歸搜尋右半部分。不過，如搜尋左半部分，我們可以跳過一些元素，值遞歸搜尋A[0]到A[3]的元素。A[3]是第一個可能成為魔術索引的元素。

綜上：我們得到一種搜尋模式，先比較midIndex和midValue是否相同。然後，若兩者不同，則按如下方式遞歸搜尋左半部分和右半部分。

左半部分：搜尋索引從start到min(midIndex-1,midValue)的元素。

右半部分：搜尋索引從max(midIndex+1,minValue)到end的元素。

可以看做前面的基礎上求左右兩邊的交集，例如A[mid]<mid，需要搜尋mid左邊的部分元素，即區間從start到min(midIndex-1,midValue)的元素和mid右邊的全部元素。

A[mid]>mid，需要搜尋mid左邊的全部元素和右邊的部分元素，即區間從max(midIndex+1,minValue)到end，然後兩者求交集，就得到上面的區間了。

完整代碼：