Java 折半查找法（二分法）【小案例详解】

墨蓝 2022-03-25 00:34 277阅读 0赞

##### 介绍 #####

折半查找法是效率较高的一种查找方法。假设有已经按照从小到大的顺序排列好的五个整数a0~a4，要查找的数是X，其基本思
    想是： 设查找数据的范围下限为l=0，上限为h=4，求中点m=（l+h）/2，用X与中点元素am比较，若X等于am，即找到，停
    止查找；否则，若X大于am，替换下限l=m+1，到下半段继续查找；若X小于am，换上限h=m-1，到上半段继续查找；如此重复
    前面的过程直到找到或者l>h为止。如果l>h，说明没有此数，打印找不到信息，程序结束。
    该方法是查找的范围不断缩小一半，所以查找效率较高。

##### 小案例需求 #####

定义一个函数接收一个数组对象和一个要查找的目标元素，函数要返回该目标元素在数组中的索引值，如果目标元素不存在数组中，那么返回-1表示。

##### 思路 #####

![在这里插入图片描述][20190117212903709.png]

##### 小代码 #####

public class Text {
        
    	public static void main(String[] args) {
        
    		
    		int[] arr= {
        12,16,19,23,54};  //定义已经排好顺序的数组
    		int index = halfSearch(arr,23); //定义一个变量对其进行存储
    		System.out.println("元素所在的索引值是："+index);
    	}
    
    	public static int halfSearch(int[] arr,int target) {
        
    		//定义三个变量分别记录最大、最小、中间的查找范围索引值
    		int max=arr.length-1;
    		int min=0;
    		int mid=(max+min)/2;
    		
    		while(true) {
        
    			
    			if(target<arr[mid]) {
        		//如果目标元素小于中点元素
    				max = mid-1;			//max向mid前移动
    			}else if(target>arr[mid]) {
         //如果目标元素大于中点元素
    				min = mid+1;			//min向mid后移动
    			}else {
        
    				return mid;				//找到目标元素
    			}
    			
    			//没有找到的情况
    			if(max<min) {
        
    				return -1;
    			}
    			
    			//重新计算中间索引值
    			mid=(max+min)/2;
    		}
    		
    	}
    }

##### 效果 #####

![在这里插入图片描述][20190117212111980.png]

[20190117212903709.png]: /images/20220325/07b96af63d914dd7b0bd101749f725c0.png?
[20190117212111980.png]: /images/20220325/b785bd4db6e04e30b84af8488d08fd84.png