首页 > 代码库 > careercup-递归和动态规划 9.3
careercup-递归和动态规划 9.3
9.3 在数组A[0...n-1]中，有所谓的魔术索引，满足条件A[i]=i。给定一个有序整数数组，元素值给不相同，编写一个方法，在数组A中找出一个魔术索引，若存在的话。
进阶：
如果数组元素有重复值，又该如何处理。？
解法一，选择蛮力法，我们可以直接迭代访问整个数组，找出符号条件的元素。
int magicSlow(int arr[],int n){ if(n==0) return -1; int i; for(i=0;i<n;i++) { if(arr[i]==i) return i; } return -1;}
解法二：既然给的数组是有序的，我们理应充分利用这个条件。
你看你会发现这个问题与经典的二分查找问题非常相似。充分运用匹配法，就能找到适当的算法，我们又该怎样运用二分查找法呢？
在二分查找中，要找出元素k，我们会先拿它跟数组中间的元素x比较，确定k位于x的左边还是右边。
以此为基础，是否通过检查中间元素就能确定魔术索引的位置？
通过比较A[mid]<mid，可以确定该魔术索引一定在mid的右边，因此left=mid+1;
如果A[mid]>mid，可以取得该魔术索引一定在mid 的左边，因此right=mid-1；
算法如下：
int magicQuick(int arr[],int n){ if(n==0) return -1; int mid; int left=0; int right=n-1; while(left<=right) { mid=(left+right)/2; if(mid==arr[mid]) return mid; else if(mid<arr[mid]) right=mid-1; else left=mid+1; } return -1;}
进阶：
如果存在重复元素，前面的算法就会失效。以下面的数组为例：
-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);}
完整代码：
#include<iostream>using namespace std;int magicSlow(int arr[],int n){ if(n==0) return -1; int i; for(i=0;i<n;i++) { if(arr[i]==i) return i; } return -1;}int magicQuick(int arr[],int n){ if(n==0) return -1; int mid; int left=0; int right=n-1; while(left<=right) { mid=(left+right)/2; if(mid==arr[mid]) return mid; else if(mid<arr[mid]) right=mid-1; else left=mid+1; } return -1;}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);}int main(){ int arr[10]={-1,0,1,2,3,4,5,6,7,9}; cout<<magicSlow(arr,10)<<endl; cout<<magicQuick(arr,10)<<endl; cout<<magicFast(arr,10)<<endl;}
careercup-递归和动态规划 9.3