魔术索引I

[编程题]魔术索引I

热度指数：10519 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

已知数组A[0..n-1]和数组大小n（升序数组，元素值各不相同），若存在A[i]=i则称该数组有魔术索引，请判断该数组是否存在魔术索引，返回值为bool，要求复杂度优于o(n)。

测试样例：

[1,2,3,4,5]

返回：false

算法知识视频讲解

Python

华科平凡

python solution:

# -*- coding:utf-8 -*-
class MagicIndex:
    def findMagicIndex(self, A, n):
        # write code here
        for i,v in enumerate(A):
            if i==v:
                return True
        return False

发表于 2017-10-01 22:33:48 回复(1)

Python

Yannyezixin

题目要求复杂度小于O(n)。那么说明用蛮力法是不可取的

题目中给出的有序数组，要找到是否有魔术索引，我们可以想到二分查找。其实这个题目也就是二分查找。

A[mid] > mid 说明mid后面的元素都大于元素的索引

A[mid] < mid 说明mid前面的元素都小于元素的索引

# -*- coding:utf-8 -*-
class MagicIndex:
    def findMagicIndex(self, A, n):
        if n < 1 or A[0] > 0 or A[n - 1] < n - 1:
            return False
        
        return self.find(A, 0, n - 1)
    
    def find(self, A, start, end):
        if start == end and A[start] != start:
            return False
        mid = (start + end)/2    
        
        if A[mid] == mid:
            return True
        elif A[mid] > mid:
            return self.find(A, start, mid - 1)
        else:
            return self.find(A, mid + 1, end)

编辑于 2016-08-04 22:49:16 回复(0)