Java中的二分查找

柔情只为你懂 2022-05-04 06:26 143阅读 0赞

基本查找：数组元素无序，从头到尾查找  
二分查找：数组元素有序，折半查找

如果有一个无序数组，先对其进行排序，之后再调用二分法查找指定元素的索引可以吗？  
  不可以，因为排序后数组的索引会发生变化，二分法查找得到的索引为元素在排序后数组中的索引。

二分查找最关键的是去找中间值  
具体步骤如下：  
假设有一个已经按照从小到大排好顺序的数组a\[\]，想查找的数据为x（数组a\[\]中有元素x）  
1、设置最小索引为min=0，最大索引为max=a.length-1，中间值mid=（min+max）/2  
2、比较元素x和元素a\[mid\]的大小  
  如果a\[mid\]>x，设置max=mid-1，min值不改变，mid=（min+max）/2  
  如果a\[mid\]=x则查找结束，返回此时的mid  
  如果a\[mid\]<x，设置min=mid+1，max值不变，mid=（min+max）/2  
3、重复步骤2的操作

这里有必要说明下Array类中已经给出了二分法寻找数组元素索引的静态方法，可以直接调用  
方法：  
  public static int binarySearch(int \[\]a,int key)  
调用格式：  
  int index=Array.binarySearch(a,value)//此处的a为数组，value为数组中的元素，index为元素索引。

**二分查找代码实例：**

package test06_chazhao;
    
    //二分法查找
    
    public class ArraryResearch {
        
    	
    	public static void main(String[] args) {
        
    		int []a= {
        13,15,21,65,78,99};
    		int value=78;
    		int index=getIndex(value,a);
    		if(index!=-1) {
        
    			System.out.println("元素"+value+"在数组中的索引是"+index);
    		}
    		else {
        
    			System.out.println("数组中无元素"+value);
    		}
    		
    	}
    	public static int getIndex(int value,int []a) {
        
    		
    		int min=0,max=a.length-1;
    		int mid;
    		
    		mid=(max+min)/2;
    		
    		while(value!=a[mid]) {
        
    			
    			if(value>a[mid]) {
        
    				min=mid+1;
    			}
    			else if(value<a[mid]) {
        
    				max=mid-1;
    			}
    			mid=(max+min)/2;
    			
    			//如果value不是数组a[]中的元素则一直在while中死循环
    			//改进，如果value不是数组中的元素则返回-1
    			if(max<min){
        
    				return -1;
    			}
    			
    		}
    		
    		
    		return mid;
    	} 
    }