查找算法入门教程-二分查找法

关于我们常见的算法其实还有一种叫二叉堆的算法,由于涉及到二叉树的知识学习,这里就先不说了,等到后面来讲,本节我们来学习常见的查找算法-二分查找,首先来了解下什么是二分查找算法?

二分查找算法

二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法.注意:采用二分查找算法的线性表必须是有序的.接着我们通过案例来分析

案例思路分析

假设我有一组有序的线性表{1,8,10,89,1000,1234}我们输入一个数,看看该数是否存在于该线性表中,同时求出它的下标,如果没有,就提示不存在该数.

首先我们来进行思路分析

• 1.我们来确定该有序列表的中间下标即:int mid = (left + right) /2
• 2.然后让需要查找的数findVal和中间下标所对应数arr[mid]进行比较
• 2.1.如果findVal>arr[mid],则说明我们要找的数在mid的右边,因此需要我们递归去找
• 2.2.如果findVal<arr[mid],则说明我们要找的数在mid的左边,因此需要我们递归去找
• 2.3.如果findVal==arr[mid],则说明我们找到了,就返回mid即可

上述就是二分查找的思路分析,其实我们发现不难,有个问题我们需要考虑清楚,我们都知道在使用递归时,我们一定要知到结束递归的条件,这很重要,通过我们对上述案例的分析发现结束递归的条件是:

• (1) .只要我们找到了就返回,这样我们的递归就结束了

那么问题来了,假如没找到了?我们结束递归的条件又是什么吗?答案我们后面见揭晓,看完了思路分析我们通过代码的方式来实现上述案例的查找过程

代码实现

//二分查找的前提是数组必须是有序的

/**
 *
 * @param arr 要查找的数组
 * @param left 左边下标
 * @param right 右边下标
 * @param findVal 要查找的数
 */
public static int binarySearch(int[] arr,int left,int right,int findVal){
    //定义中间变量索引并初始化
    int mid = (left + right) /2;
    //获取中间变量索引对应的下标
    int midVal = arr[mid];
    //如果找不到,我们结束递归的条件是left > right
    if (left > right){
        return -1;
    }
    //进行查找
    if (findVal >midVal){ //表示要查找的值在右边,我们递归处理
        //说明: 右边查找我们需要改变左边的下标也就是从 mid+1处开始去递归处理结果
        return binarySearch(arr,mid +1,right,findVal);
    }else if (findVal < midVal) {
        //表示要查找的值在左边,我们递归处理
        //说明: 左边查找我们需要改变右边的下标也就是从 left - mid-1之间去递归处理结果
        return binarySearch(arr,left,mid -1,findVal);
    }else {
        return mid;
    }
}

不知道大家发现了没.如果假如没有找到的话,结束递归的条件是如下这段代码

//如果找不到,我们结束递归的条件是left > right
    if (left > right){
        return -1;
    }

你想啊,在递归查找的过程中,如果第一次没找到,我们left索引向前移动,right索引则需要 --操作,如果一直一直递归找,left > right的话,表示要找的数是不存在的,我们就需要结束递归了.我们来测试一把

测试代码

''''
/**
* 查找算法-二分查找法
 */
public class BinarySearch {
public static void main(String[] args) {
    int [] arr = {1,8,10,89,1000,1234};
    int result = binarySearch(arr, 0, arr.length - 1, 55);
    System.out.println("result ="+result);

• 测试结果如下:

  
  测试结果1.png

上述是在找一个不存的数,我们发现返回-1,此时是因为我们加了结束递归的条件的,我们再来测一把不加添加的情况

测试结果2.png

去掉条件时,我们发现会报栈溢出,因为找不到递归结束的条件,所以在使用递归时特别注意这点,我们在来测试一下存在的数,我们来找1000这个数

测试结果3.png

接下来我们来看下这样一个需求:我有这样一个有序列表 {1,8,10,89,1000,1000,1000,1234},我需要找出1000的的所对应的下标,看完需求我们来分析下:

• 1.在我们找到mid下标值时,不要立即返回
• 2.在mid下标值的左边进行扫描,我们将所有满足1000元素的下标找到后存放在List中
• 3.在mid下标值的右边进行扫描,我们将所有满足1000元素的下标找到后存放在List中
• 4.最后返回list

最后发现,所有的处理过程是在我们找到mid的时候进行相关的处理,我们来看代码实现

代码升级

public static List binarySearch2(int[] arr, int left, int right, int findVal){
    //定义中间变量索引并初始化
    int mid = (left + right) /2;
    //获取中间变量索引对应的下标
    int midVal = arr[mid];
    //如果找不到,我们结束递归的条件是left > right
    if (left > right){
        return new ArrayList();
    }
    //进行查找
    if (findVal >midVal){ //表示要查找的值在右边,我们递归处理
        //说明: 右边查找我们需要改变左边的下标也就是从 mid+1处开始去递归处理结果
        return binarySearch2(arr,mid +1,right,findVal);
    }else if (findVal < midVal) { //表示要查找的值在左边,我们递归处理
        //说明: 左边查找我们需要改变右边的下标也就是从 left - mid-1之间去递归处理结果
        return binarySearch2(arr,left,mid -1,findVal);
    }else {
        List<Integer> list = new ArrayList<>();
        //定义一个临时的变量来存储我们的找到的索引
        int temp = mid -1;
        //在mid下标值的左边进行扫描,我们将所有满足1000元素的下标找到后存放在List中
        while (true){
            if (temp <0 || arr[temp] !=findVal){ //表示极限条件,我们不需要操作,直接退出
                    break;
            }
            list.add(temp);
            temp --; //继续找
        }
        list.add(mid); //将当前已经找到的也存放在list中
        //在mid下标值的右边进行扫描,我们将所有满足1000元素的下标找到后存放在List中
        temp = mid +1; //右边处理过程
        while (true){
            if (temp > arr.length -1 || arr[temp] !=findVal){ //右边遍历完了,没有找到的话直接退出
                break;
            }
            //找到了就添加
            list.add(temp);
            temp ++; //继续找
        }
        return list;
    }
}

• 测试结果如下图:

  
  测试结果4.png

那么关于二分查找的学习就到这里了...