在数组中找到m，使得Arr [m] = m（O（logn）中的m]

Question

我有一个已知长度的排序数组，在​​该数组中需要查找一个元素，使得该元素的值等于其索引。如果M是Array中的元素，则它应满足条件Array [M] = M。

Answer 1

这可以通过修改后的二进制搜索完成。

算法：

检查中段=（开始+结束）/ 2，使用A [中段]，检查A [中段] =中段。如果是，则返回中点。

[如果mid> A [mid]表示不动点可能在数组的右半部分，则递归调用search（A，mid + 1，end）。

如果mid

实施：

public class MagicIndex {
    // perform modified binary search
    public int search(int[] A, int start, int end) {
        if (start <= end) {
            int mid = (start + end) / 2;
            if (mid == A[mid]) // check for magic index.
                return mid;
            if (mid > A[mid]) { // If mid>A[mid] means fixed point might be on
                                // the right half of the array
                return search(A, mid + 1, end);
            } else {// If mid<A[mid] means fixed point might be on
                // the left half of the array
                return search(A, start, mid - 1);
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] A = { -1, 0, 1, 2, 4, 10 };
        MagicIndex m = new MagicIndex();
        System.out.println("Magic index " + m.search(A, 0, A.length - 1));
    }

}