魔术索引算法

题目介绍

在数组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;
}