二分查找算法详解

系统管理员 2024-03-27 14:41 7阅读 0赞

## 1. 简介 ##

我们对数组除了可以进行排序之外，还能对数组中的元素进行查找，其中一个比较经典的方案是利用二分查找法，也叫做折半查找法进行实现，可以缩小查找范围，提高查找效率。

二分查找是一种效率较高的查找方法，要求数据表须采用顺序存储结构，且数组是有序(升序或者降序)的。**核心思路就是将待查找的元素与中间下标对应的元素进行比较，如果大于中间下标对应的元素，则去右半部分查找，否则就去左半部分进行查找。基本实现流程如下：**

● **首先，我们假设数组中的元素是按升序排列的；**

● **然后将数组中间位置记录的关键字与查找关键字进行比较，如果两者相等，则查找成功；**

● **否则就利用中间的位置记录，将数组分成前、后两个子部分。如果中间位置记录的关键字大于查找关键字，则进一步查找前一子部分，否则进一步查找后一子部分；**

● **重复以上过程，直到找到满足条件的记录为止。或直到子部分不存在为止，此时查找不成功。**

## 2. 实现案例 ##

然后就按照上述思路，给大家设计了如下案例，大家可以对照练习，好好琢磨该案例。

public class Demo14 {
    
    	public static void main(String[] args) {
    		// 二分查找法--折半查找法
    
    		// 遍历排序后的数组
    		int[] arr = { 1, 3, 46, 22, 11 };
    
    		int index = search(arr,46);
    		System.out.println("46所在的索引位置="+index);
    	}
    	
    	//定义一个方法，实现二分查找
    	public static int search(int[] arr,int num) {
    	    //1. 获取最小、大值的下标
    	    int min = 0;
    	    int max = arr.length -1;
    
    	    while(min <= max) {
    	        //2. 获取中间值的下标
    	        int middle = (min + max) / 2;
    
    	        //3. 将要查找的数字与中间值做比较
    	        if(num > arr[middle]) {
    	            min = middle +1;
    	        }else if(num < arr[middle]) {
    	            max = middle -1;
    	        }else {
    	            return middle;
    	        }
    	    }
    	    return -1;
    	}
    
    }