java中的数组元素查找

小鱼儿 2022-05-25 20:36 283阅读 0赞

数组元素查找有很多中方法，我们先来看最简单的一种

public class Ac{
    	public static void main(String [] args){
    		int [] numbers={1,2,3,4,5,6,7,8,9,10};
    		int data=8;
    		for(int number : numbers){
    			System.out.println("**********");
    			if(data==number){
    				System.out.println("Yes");
    				return;
    			}
    		}
    		System.out.println("No");
    
    	}
    }

我们运行后可以得到结果：

\*\*\*\*\*\*\*\*\*\*  
\*\*\*\*\*\*\*\*\*\*  
\*\*\*\*\*\*\*\*\*\*  
\*\*\*\*\*\*\*\*\*\*  
\*\*\*\*\*\*\*\*\*\*  
\*\*\*\*\*\*\*\*\*\*  
\*\*\*\*\*\*\*\*\*\*  
\*\*\*\*\*\*\*\*\*\*  
Yes  
可以看出这种方法虽然简单，但性能却非常低。  
下面我们介绍一种性能很好的二分法查找

public class ChaZhao{
    	public static void main(String [] args){
    		
    	
    		int [] numbers={1,2,3,4,5,6,7,8,9,10};
    		int data=8;
    		int high=numbers.length-1;
    		int low=0;
    		int middle;
    		while(low<=high){
    			middle=(high+low)/2;
    			if(numbers[middle]==data){
    				System.out.println("Yes");
    				return;
    			}else if(numbers[middle]<data){
    				low=middle+1;
    			}else if(numbers[middle]>data){
    				high=middle-1;
    			}
    		}
    		System.out.println("No");
    	}
    }

其原理是：我们先找到数组的最中间的元素，将待查找数与中间数进行比较，如果待查找数比中间数大那就将查找范围控制在数组后半段，反之就是将查找范围控制在数组后半段，以此类推，直到找到了那个数或者是查找范围的最小数或最大数超出边界。（前提条件是数组本来是有序的）。  
运行结果：  
\*\*\*\*\*\*\*\*\*\*  
\*\*\*\*\*\*\*\*\*\*  
Yes  
可以看到二分法查找的效率是很高的。