魔术索引2

题目描述

在数组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的元素。

class MagicIndex {
public:bool findMagicIndex(vector<int> A, int n) {// write code herereturn findMagicIndexCore(A,0,A.size()-1) == -1?false:true;}int findMagicIndexCore(vector<int> A,int start,int end){if(end0 || 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;}
};

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！