Index Equals to Value

出处

Find i in a given array that arr[i] == i.

Solution

本题最直观的想法是线性扫描整个数组,逐一检查元素值与下标是否相同。这样做的时间复杂度是O(n),但是很明显的缺陷在于这种做法完全没有利用到数组是有序的特性。由于题目中出现了关键字“sorted”,结合“The Rules”中提到的规律:对于有序线性容器的搜索,二分查找或其变种基本上是解题的最佳方法,我们需要尝试设计一种类似于二分查找的算法。通常,我们可以尝试自己举个实例,便于发现普遍规律性:

Index 0 1 2 3 4 5 6 7 8
Value -7 -2 0 3 7 9 10 12 13

在此例中,A[3] = 3。同时,不难发现一个规律:A[3]左侧的数据满足value < index,A[3]右侧的数据满足value > index。反而言之,如果当前数据满足value < index,则需要搜索的数据必然在其右侧,如“果当前数据满足value > index,则需要搜索的数据必然在其左侧。这样,实际上就可以利用二分查找:比较当前数据值和其下标,选择恰当的半边进行下一步搜索。

Complexity

时间复杂度同二分查找,为O(logn)。

Code

非递归方法

int indexSearch(int[] arr){
    int len = arr.length;
    int low = 0;
    int high = len - 1;
    while (low =< high){
        int mid = (low + high) / 2;
        if (mid == arr[mid]){
            return mid;
        } else if (mid > arr[mid]){
            low = mid + 1;
        } else {
            high = mid - 1;         
        }
    }
    return -1;
}

递归方法

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

可能有重复的情况

int magicIndex1(int[] array){
    for (int i = 0; i < array.length; i++){
        if (array[i] == i){
            return i;
        }
    }
    return -1;
}

int magicIndex2(int[] array){
    int start = 0;
    int end = array.length - 1;

    while (end > start){
        int mid = (start + end) / 2;
        if (array[mid] == mid){
            return mid;
        }
        else if (array[mid] > mid){
            end = mid - 1;
        }
        else {
            start = mid + 1;
        }
    }
    return -1;
}

// FOLLOW UP, Use the solution to help understanding
int magicFast3(int[] array){
    return magicFast3(array, 0, array.length - 1);
}

int magicFast3(int[] array, int start, int end){
    if (end < start)
        return -1;

    int midIndex = (start + end) / 2;
    int midValue = array[midIndex];
    if (midValue == midIndex){
        return midIndex;
    }

    // search left
    int leftIndex = Math.min(midIndex - 1, midValue);
    int left = magicFast3(array, start, leftIndex);
    if (left >= 0){
        return left;
    }

    // seach right
    int rightIndex = Math.max(midIndex + 1, midValue);
    int right = magicFast3(array, rightIndex, end);

    return right;
}