java数据结构之折半查找

分手后的思念是犯贱 2023-10-18 11:09 106阅读 0赞

**折半查找，也称二分法查找、二分搜索，是一种在有序数组中查找某一特定元素的搜索算法，这里强调有序表明这种算法的特定使用场景；**

**搜素过程为，从数组中间元素开始，如果中间元素正好是要查找的元素，则搜素过程结束；**

**如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组已经为空，则表示找不到指定的元素。这种搜索算法每一次比较都使搜索范围缩小一半，相比顺序查找，其时间复杂度是O(logN)；**

折半查找的精髓在于这个折半的程序代码的编写，这里将使用两种方式进行折半查找，第一张是按照上述解释的意思，每次排除一般的数据，另一种方式是，考虑到查找的过程的重复性，使用递归算法进行查找，下面上代码，

1、给定一个有序数组，再给定一个特定的数据，如果这个数据存在于这个数组中，返回数据对应的下标，否则返回-1，代码比较简单，相信大家一看就懂；

public class TestSearch {
    	
    	public static void main(String[] args) {
    		//定义一个数组
    		int[] searchArr = {1,2,3,4,5,6,7,8,9,10};
    		//给定要查找的数
    		int num = 5;
    		//执行查找
    		int index = -1;
    		for(int i=0;i<searchArr.length;i++){
    			if(num == searchArr[i]){
    				index = i;
    			}
    		}
    		if(index == -1){
    			System.out.println("没有找到");
    		}else{
    			System.out.println("找到了这个数，在数组中的下标是:" + index );
    		}
    	}
    }

**2、下面用折半查找第一种方式来做**

/**
    	 * @param arr  给定数组
    	 * @param key  要查找的值
    	 * @return
    	 */
    	public static int doSearch(int[] arr,int key){
    		//指定一个最小值
    		int low = 0;
    		//指定最大值
    		int high = arr.length - 1;
    		//判断key和middle的关系
    		while(low <= high){
    			//初始化指定一个中间值
    			int middle = (low + high)/2;
    			if(key == arr[middle]){
    				return middle;
    			}else if(key < arr[middle]){
    				high = middle - 1;
    			}else if(key > arr[middle]){
    				low = middle + 1;
    			}
    		}
    		return -1;
    	}

**然后再在main函数中调用，**

public static void main(String[] args) {
    		int[] array = {1,2,3,4,5,6,7,8,9,10};
    		//给定要查找的数据
    		int key = 3;
    		//执行查找的流程，不使用递归
    		int index = doSearch(array, key);
    		//折半查找，采用递归算法
    		//int index = bianarySearch(array,key);
    		//输出结果
    		if(index == -1){
    			System.out.println("要查找的数据不存在");
    		}else{
    			System.out.println("数据所在的下标是:" + index);
    		}
    	}

运行，可以看到要查找的结果是否在我们的数组中，

**下面采用递归的方式进行查找，**

/**
    	 * 递归进行折半查找数据
    	 * @param arr
    	 * @param key
    	 * @return
    	 */
    	public static int bianarySearch(int[] arr,int key){
    		int low = 0;	//从0开始
    		int high = arr.length - 1;
    		return doSearchForDiGui(arr,key,low,high);
    	}
    	
    	/**
    	 * 递归方式查找
    	 * @param arr	给定数据
    	 * @param key	要查找的数据
    	 * @param low	最小下标
    	 * @param high	最大下标
    	 * @return
    	 */
    	public static int doSearchForDiGui(int[] arr,int key,int low,int high){
    		if(low > high){
    			return -1;
    		}
    		int middle = (low +high)/2;
    		if(key == arr[middle]){
    			return middle;
    		}else if(key < arr[middle]){
    			return doSearchForDiGui(arr,key,low,middle-1);
    		}else{
    			return doSearchForDiGui(arr,key,middle+1,high);
    		}
    	}

然后再在main函数中调用，

public static void main(String[] args) {
    		int[] array = {1,2,3,4,5,6,7,8,9,10};
    		//给定要查找的数据
    		int key = 3;
    		//执行查找的流程，不使用递归
    		//int index = doSearch(array, key);
    		//折半查找，采用递归算法
    		int index = bianarySearch(array,key);
    		//输出结果
    		if(index == -1){
    			System.out.println("要查找的数据不存在");
    		}else{
    			System.out.println("数据所在的下标是:" + index);
    		}
    	}

运行，可以看到要查找的结果是否在我们的数组中