魔術索引算法

題目介紹

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

蠻力法

周遊整個數組，遇到符合條件的元素，傳回索引。若沒有符合條件的元素，傳回-1。

蠻力法實作：

public static int magicBruteForce(int[] arr){
    for (int i = 0; i < arr.length; i++) {
        if(arr[i] == i) return i;
    }
    return -1;
}           

時間複雜度：O(n)。

二分查找法

因為數組是有序的，我們可以用二分查找法，将時間複雜度降到O(lgn)。

二分查找法: 通過不斷将要搜素的間隔分裂成一半，來搜尋一個已經排好序的數組。首先，一個間隔覆寫整個數組。如果搜尋鍵的值小于間隔中間的項,将搜尋區間縮小一半（留值小的一半）。否則将搜尋區間縮小一半（留值大的一半）。反複檢查間隔,直到找到要找的值或者間隔已經是空的。

step1:

mid = 5, A[mid] = 12;

A[mid] > mid;

留左半邊數組；

step2:

mid = 2, A[mid] = 1;

A[mid] < mid;

留右半邊數組；

step3:

mid = 3, A[mid] = 3;

A[mid] == mid;

傳回索引mid;

二分查找法實作：

public static int magicBinary(int[] arr){
    return magicBinary(0, arr.length-1, arr);
}

private static int magicBinary(int low, int high, int[] arr){
    if(low > high) return -1;
    int mid = (low + high)/2;
    if(arr[mid] == mid) return mid;
    else if(arr[mid] > mid) return magicBinary(low, mid - 1, arr);
    else return magicBinary(mid + 1, high, arr);
}           

時間複雜度：O(lgn)。

進階：如果數組元素有重複值

觀察上圖，我們可以看到當有重複值時，A[mid] < mid時，搜尋右半邊不再成立。此時魔術索引可以在數組右側(A[1])，也可以在左側(A[8])。

根據上圖的例子，那是不是說魔術索引可以在左邊或右邊的任意位置？當然不是！

其實，我們可以看到A[5] = 3 時，魔術索引隻可能存在于A[0]到A[3]之間。是以，我們在搜尋時可以跳過一些元素。

綜上所述，有重複值時我們的搜尋邏輯為：

1. A[mid] == mid, 傳回索引mid, 結束搜尋；
2. 搜尋左半部分：low不變，high = min(mid-1, A[mid])
3. 搜尋右半部分：high不變，low = max(mid+1, A[mid])

代碼實作：

public static int magicBinaryDup(int[] arr){
    return magicBinaryDup(0, arr.length-1, arr);
}

private static int magicBinaryDup(int low, int high, int[] arr){
    if(low > high) return -1;
    int mid = (low + high)/2;
    if(arr[mid] == mid) return mid;

    //left part
    int highLeft = Math.min(mid - 1, arr[mid]);
    int leftResult =  magicBinaryDup(low, highLeft, arr);
    if(leftResult > 0) return leftResult;
    
    //right part
    int lowRight = Math.max(mid + 1, arr[mid]);
    int rightResult = magicBinaryDup(lowRight, high, arr);
    return rightResult;
}