魔术索引

/**
 * 功能：在数组A[0…n-1]中，有所谓的魔术索引，满足条件A[i]=i。
 * 给定一个有序整数数组，元素值各不相同，找出一个魔术索引。
 * 
 * 进阶：如果数组元素有重复值，如何处理

 */

两种方法：

方法一：

[java] view plain copy

1. //穷举法  
2. public static int getMagicIndex(int[] array){  
3.     for(int i=0;i<array.length;i++){  
4.         if(array[i]==i)  
5.             return i;  
6.     }  
7.     return -1;  
8. }  

方法二：

[java] view plain copy

1. //二分查找法  
2. /** 
3.  * 思路:利用数组有序的特点，运用模式匹配法。 
4.  * @param array 
5.  * @return 
6.  */  
7. public static int getMagicIndex2(int[] array){  
8.     return judge(array,0,array.length-1);  
9. }  
10.   
11. public static int judge(int[] array,int start,int end){  
12.     if(end<start||start<0||end>array.length)  
13.         return -1;  
14.       
15.     int mid=(start+end)/2;  
16.     if(array[mid]==mid)  
17.         return mid;  
18.     else if(array[mid]<mid)  
19.         return judge(array,mid+1,end);  
20.     else   
21.         return judge(array,start,mid-1);          
22. }  

进阶：

[java] view plain copy

1. //进阶：如果数组元素有重复值  
2. public static int getMagicIndex3(int[] array){  
3.     return judge2(array,0,array.length-1);  
4. }  
5.   
6. public static int judge2(int[] array,int start,int end){  
7.     if(end<start||start<0||end>array.length)  
8.         return -1;  
9.       
10.     int midIndex=(start+end)/2;  
11.     int midValue=array[midIndex];  
12.     if(midIndex==midValue)  
13.         return midIndex;  
14.   
15.     //搜索左半部分   
16.     int leftIndex=Math.min(midIndex-1, midValue);  
17.     int left=judge2(array,start,leftIndex);  
18.     if(left>=0)  
19.         return left;  
20.       
21.     //搜索右半部分  
22.     int rightIndex=Math.max(midIndex+1, midValue);  
23.     int right=judge2(array,rightIndex,end);  
24.       
25.     return right;  
26. }