Magic Index

https://www.cnblogs.com/wuchanming/p/4149788.html
http://www.voidcn.com/article/p-ofbkvbvl-bkw.html

在数组A[0..n-1]中，有所谓的魔术索引，满足条件A[i]=i。给定一个升序数组，元素值各不相同，编写一个方法，判断在数组A中是否存在魔术索引。请思考一种复杂度优于o(n)的方法。
给定一个int数组A和int n代表数组大小，请返回一个bool，代表是否存在魔术索引。
测试样例：
[1,2,3,4,5]
返回：false

解答

暴力法

class MagicIndex {
public:
    bool findMagicIndex(vector<int> A, int n) {
        // write code here
        for(int i = 0;i<n;++i)
            if(A[i] == i)
                return true;

        return false;
    }
};

根据数据特点，利用二分查找的思想

　　给定的数组是有序的。
　　这个问题域经典的二分查找非常相似。在二分查找中，要找出元素k，我们会先拿它跟数组中间的元素x比较，确定k是位于x的左边还是右边。
　　以此为基础，是否可以通过检查中间元素来确定魔术索引的位置？
　　
　　以上面的数组为例，看到中间元素A[5] = 3，由于A[mid]

    bool findMagicIndex(vector<int> A, int n) {
        // write code here
        return findMagicIndexCore(A,0,A.size()-1) == -1?false:true;

    }

    int findMagicIndexCore(vector<int> A,int start,int end)
    {
        if(end<start || start < 0 || end>=A.size())
            return -1;
        int mid = (start+mid)/2;
        if(A[mid] == mid)
            return mid;
        else if(A[mid] < mid)
            return findMagicIndexCore(A,mid+1,end);
        else
            return findMagicIndexCore(A,start,mid-1);
    }

X. https://www.cnblogs.com/wuchanming/p/4149788.html

如果存在重复元素，前面的算法就会失效。以下面的数组为例：

-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，然后两者求交集，就得到上面的区间了。

int magicHelper(int arr[],int n,int l,int r)
{
    if(l>r||l<0||r>=n)
        return -1;
    int mid=(l+r)/2;
    if(mid==arr[mid])
        return mid;
    int rightindex=min(mid-1,arr[mid]);
    int left=magicHelper(arr,n,l,rightindex);
    if(left>=0)
        return left;
    int leftindex=max(mid+1,arr[mid]);
    int right=magicHelper(arr,n,leftindex,r);
    return right;
}
//有重复元素
int magicFast(int arr[],int n)
{
    if(n==0)
        return -1;
    return magicHelper(arr,n,0,n-1);
}

http://www.voidcn.com/article/p-rkooanvq-bkw.html

在数组A[0..n-1]中，有所谓的魔术索引，满足条件A[i]=i。给定一个不下降序列，元素值可能相同，编写一个方法，判断在数组A中是否存在魔术索引。请思考一种复杂度优于o(n)的方法。
给定一个int数组A和int n代表数组大小，请返回一个bool，代表是否存在魔术索引。
测试样例：
[1,1,3,4,5]
返回：true

解答

　　如果数组的元素有重复，魔术索引1中的方法就会失效。以下面的数组为例
　　
　　可以看到A[mid] < mid时，我们无法判定魔术索引位于数组的哪一边。
　　它是否可能在左侧的任意位置？不是。由A[5]=3，可以知道，A[4]不可能是魔术索引。A[4]=4，它才能是魔术索引，但数组是有序的，索引A[4]必定小于等于A[5]。
　　所以，我们可以将算法分为两步
　　

1. 比较midIndex与midValue，若二者相同，直接返回。
2. 否按照如下的方式，递归搜索数组的左半部分和右半部分：
   左半部分：搜索从start到min（midIndex-1,midValue）的元素；
   右半部分：搜索从max（midIndex+1,midValue）到end的元素。

    bool findMagicIndex(vector<int> A, int n) {
        // write code here
        return findMagicIndexCore(A,0,A.size()-1) == -1?false:true;
    }

    int findMagicIndexCore(vector<int> A,int start,int end)
    {
        if(end<start || start <0 || end>=A.size())
            return -1;
        int midIndex = (start+end)/2;
        int midValue = A[midIndex];
        if( midValue == midIndex)
            return midIndex;

        int leftEnd = min(midIndex-1,midValue);
        int left = findMagicIndexCore(A,start,leftEnd);
        if(left>=0)
            return left;

        int rightStart = max(midIndex+1,midValue);
        int right = findMagicIndexCore(A,rightStart,end);

        return right;

    }