魔术索引问题

电玩女神 2022-09-30 06:28 131阅读 0赞

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

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

eg:

[1,2,3,4,5,6,7] false

这题貌似很简单,但是这里有一种比较有趣的方法,这里记一下~

首先明确一下关系,如果存在一个数(注意是存在)，只要满足a\[i\]=i，就表示存在魔术索引，不难想到使用二分法来解决这个问题,也就是取中值，然后和数组的下标进行比较，如果小于值小于下标那么在右侧递归,如果值大于下标那么在左侧递归，为啥?下面看图

![Center][]

很显然这很不魔术索引

![Center 1][]

这是一个递增的数组,如果中值比下标大,那么只可能在左边存在mssy

下面贴出实现的代码:

package fff;
    
    import java.util.Scanner;
    public class Different {
    	
    	 public static boolean findMagicIndex(int[] A,int n){
    		 if(A.length!=n||A==null){
    			 return false;
    		 }
    		 
    		 return findMagic(A,0,n-1);
    	 }
    
    		
    	private static boolean findMagic(int[] a, int start, int end) {
    		// 
    		if(start>end){
    			return false;
    		}
    		int index=(start+end)/2;
    		if(a[index]==index){
    			return true;
    		}
    		if(index<a[index]){
    			return findMagic(a, start, index-1);
    		}
    		else{
    			return findMagic(a, index+1,end);
    		}
    		
    	}
    
    
    	public static void main(String[] args) {
    		Scanner sin=new Scanner(System.in);
    		int n=sin.nextInt();
    		int[] a=new int[n];
    		for(int i=0;i<n;i++){
    			a[i]=sin.nextInt();
    		}
    		System.out.println(findMagicIndex(a,n));
    	}
    }

[Center]: /images/20220708/d2380c0bc3004a34bfce2cf2fd2bebea.png
[Center 1]: /images/20220708/81ad4f75e66543c78e4b497f505550b3.png