魔术索引I

在数组A[0..n-1]中，有所谓的魔术索引，满足条件A[i]=i。给定一个升序数组，元素值各不相同，编写一个方法，判断在数组A中是否存在魔术索引。请思考一种复杂度优于o(n)的方法。

给定一个int数组A和int n代表数组大小，请返回一个bool，代表是否存在魔术索引。

测试样例：

[1,2,3,4,5]
返回：false

方法一 ：利用二分法O(logN)

也要考虑目标点在最开始或者末尾时的情况

class MagicIndex:
    def findMagicIndex(self, A, n):
        # write code here
        if A[0]<=0 and A[n-1]>=(n-1):
            pre = 0
            end = n-1

            while(pre<end):
                mid = int((pre+end)/2)
                if A[mid] == mid:
                    return True
                elif A[mid] > mid:
                    end = mid
                else:
                    pre = mid
            if A[pre] == pre:
                return True
            else:
                return False
        else:
            return False


if __name__ == '__main__':
    l = [0,2,3,4,5,6]
    s = MagicIndex()
    res = s.findMagicIndex(l,6)
    print(res)

方法二：

利用Python的enumerate

class MagicIndex:
    def findMagicIndex(self, A, n):
        for index,v in enumerate(A):
            if index == v:
                return True
        return False