首页 > 编程语言 >黑马Java零基础视频教程精华部分_15_基本查找/顺序查找、二分查找/折半查找、插值查找、斐波那契查找、分块查找、哈希查找

黑马Java零基础视频教程精华部分_15_基本查找/顺序查找、二分查找/折半查找、插值查找、斐波那契查找、分块查找、哈希查找

时间:2024-08-09 21:26:03浏览次数:14  
标签:折半 arr Java int mid 查找 return public

系列文章目录


文章目录


一、基本查找/顺序查找

核心思想:从0索引开始挨个往后查找

代码:

public class SearchWays {
    public static void main(String[] args) {
        int[] arr ={ 123,213,124,354,465,7566};
        System.out.println(basicSearch(arr, 213));

    }

    private static boolean basicSearch(int[] arr, int num){
        for (int i = 0; i < arr.length; i++) {
            if(arr[i]==num) return true;
        }
        return  false;
    }
}

练习:定义一个方法利用基本查找,查询某个元素在数组中的索引,数组包含重复数据。

public class SearchWays {
    public static void main(String[] args) {
        int[] arr ={ 123,213,124,354,465,7566,123,123,213};
        System.out.println(basicSearch(arr, 213));

    }

    private static ArrayList<Integer> basicSearch(int[] arr, int num){
        ArrayList<Integer> nums = new ArrayList<>();
        for (int i = 0; i < arr.length; i++) {
            if(arr[i]==num) nums.add(i);
        }
        return  nums;
    }
}

二、二分查找/折半查找

前提条件:元素必须是有序的,从小到大,或者从大到小都是可以的。
如果是无序的,也可以先进行排序。但是排序之后,会改变原有数据的顺序,查找出来元素位置跟原来的元素可能是不一样的,所以排序之后再查找只能判断当前数据是否在容器当中,返回的索引无实际的意义。

核心思想:属于有序查找算法。用给定值先与中间结点比较,每次排除一半的查找范围。比较完之后有三种情况:

  1. 相等:说明找到了
  2. 要查找的数据比中间节点小:说明要查找的数字在中间节点左边
  3. 要查找的数据比中间节点大:说明要查找的数字在中间节点右边

代码:

public class SearchWays {
    public static void main(String[] args) {
        int[] arr ={ 1,2,3,4,5,5,6,7,8,213};
        System.out.println(binarySearch(arr, 5));

    }

    private static ArrayList<Integer> binarySearch(int[] arr, int num){
        ArrayList<Integer> nums = new ArrayList<>();
        int left=0,right=arr.length-1;
        int mid=(left+right)/2;
        while(left<=right){
            if(arr[mid]==num){
                nums.add(1);
                return nums;
            } else if (arr[mid]>num) {
                right=mid-1;
                mid = (left+right)/2;
            }else {
                left=mid+1;
                mid = (left+right)/2;
            }
        }
        return  nums;
    }
}

三、插值查找(二分查找的改进)

在介绍插值查找之前,先考虑一个问题:
为什么二分查找算法一定要是折半,而不是折四分之一或者折更多呢?
其实就是因为方便,简单,但是如果我能在二分查找的基础上,让中间的mid点,尽可能靠近想要查找的元素,那不就能提高查找的效率了吗?
二分查找中查找点计算如下:

mid=(low+high)/2, 即mid=low+1/2*(high-low);

我们可以将查找的点改进为如下:

mid=low+(key-a[low])/(a[high]-a[low])*(high-low),

这样,让mid值的变化更靠近关键字key,这样也就间接地减少了比较次数。

核心思想:基于二分查找算法,将查找点的选择改进为自适应选择,可以提高查找效率。当然,差值查找也属于有序查找。

细节:对于表长较大,而关键字分布又比较均匀的查找表来说,插值查找算法的平均性能比折半查找要好的多。反之,数组中如果分布非常不均匀,那么插值查找未必是很合适的选择。
代码跟二分查找类似,只要修改一下mid的计算方式即可。

四、斐波那契查找(二分查找的改进)

在介绍斐波那契查找算法之前,我们先介绍一下很它紧密相连并且大家都熟知的一个概念——黄金分割。

黄金分割

  1. 黄金比例又称黄金分割,是指事物各部分间一定的数学比例关系,即将整体一分为二,较大部分与较小部分之比等于整体与较大部分之比,其比值约为1:0.618或1.618:1。
  2. 0.618被公认为最具有审美意义的比例数字,这个数值的作用不仅仅体现在诸如绘画、雕塑、音乐、建筑等艺术领域,而且在管理、工程设计等方面也有着不可忽视的作用。因此被称为黄金分割。
  3. 在数学中有一个非常有名的数学规律:斐波那契数列:1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89…….(从第三个数开始,后边每一个数都是前两个数的和)。
  4. 然后我们会发现,随着斐波那契数列的递增,前后两个数的比值会越来越接近0.618,利用这个特性,我们就可以将黄金比例运用到查找技术中。
    在这里插入图片描述

核心思想:也是二分查找的一种提升算法,通过运用黄金比例的概念在数列中选择查找点进行查找,提高查找效率。同样地,斐波那契查找也属于一种有序查找算法。

斐波那契查找也是在二分查找的基础上进行了优化,优化中间点mid的计算方式即可

代码:

public class FeiBoSearchDemo {
    public static int maxSize = 20;

    public static void main(String[] args) {
        int[] arr = {1, 8, 10, 89, 1000, 1234};
        System.out.println(search(arr, 1234));
    }

    public static int[] getFeiBo() {
        int[] arr = new int[maxSize];
        arr[0] = 1;
        arr[1] = 1;
        for (int i = 2; i < maxSize; i++) {
            arr[i] = arr[i - 1] + arr[i - 2];
        }
        return arr;
    }

    public static int search(int[] arr, int key) {
        int low = 0;
        int high = arr.length - 1;
        //表示斐波那契数分割数的下标值
        int index = 0;
        int mid = 0;
        //调用斐波那契数列
        int[] f = getFeiBo();
        //获取斐波那契分割数值的下标
        while (high > (f[index] - 1)) {
            index++;
        }
        //因为f[k]值可能大于a的长度,因此需要使用Arrays工具类,构造一个新法数组,并指向temp[],不足的部分会使用0补齐
        int[] temp = Arrays.copyOf(arr, f[index]);
        //实际需要使用arr数组的最后一个数来填充不足的部分
        for (int i = high + 1; i < temp.length; i++) {
            temp[i] = arr[high];
        }
        //使用while循环处理,找到key值
        while (low <= high) {
            mid = low + f[index - 1] - 1;
            if (key < temp[mid]) {//向数组的前面部分进行查找
                high = mid - 1;
                /*
                  对k--进行理解
                  1.全部元素=前面的元素+后面的元素
                  2.f[k]=k[k-1]+f[k-2]
                  因为前面有k-1个元素没所以可以继续分为f[k-1]=f[k-2]+f[k-3]
                  即在f[k-1]的前面继续查找k--
                  即下次循环,mid=f[k-1-1]-1
                 */
                index--;
            } else if (key > temp[mid]) {//向数组的后面的部分进行查找
                low = mid + 1;
                index -= 2;
            } else {//找到了
                //需要确定返回的是哪个下标
                if (mid <= high) {
                    return mid;
                } else {
                    return high;
                }
            }
        }
        return -1;
    }
}

五、分块查找

一般我们遇到数据没有任何顺序(使用基本查找),或者遇到数据有一定顺序(使用二分、插值、斐波那契查找)的情况都不多,一般遇到的都是无序当中又透露着有序,这时候需要使用分块查找。如下图所示,块内无序,块与块之间有序。
在这里插入图片描述
分块的原则1:前一块中的最大数据,小于后一块中所有的数据(块内无序,块间有序。
分块的原则2:块数数量一般等于数字的个数开根号。比如:16个数字般分为4块左右

核心思想:先确定要查找的元素在哪一块,然后在块内挨个查找

我们需要定义一个类来存放每个块的一些数据,如下图所示:
在这里插入图片描述
然后把块放到索引表中,如下图所示:
在这里插入图片描述
索引表具体如下图所示:可以用二分查找或者基本查找找到目标数字在哪一块中。
在这里插入图片描述

分块查找的过程:

  1. 需要把数据分成N多小块,块与块之间不能有数据重复的交集。
  2. 给每一块创建对象单独存储到数组当中
  3. 查找数据的时候,先在数组查,当前数据属于哪一块
  4. 再到这一块中顺序查找

代码:

package com.itheima.search;

public class A03_BlockSearchDemo {
    public static void main(String[] args) {
        /*
            分块查找
            核心思想:
                块内无序,块间有序
            实现步骤:
                1.创建数组blockArr存放每一个块对象的信息
                2.先查找blockArr确定要查找的数据属于哪一块
                3.再单独遍历这一块数据即可
        */
        int[] arr = {16, 5, 9, 12,21, 18,
                     32, 23, 37, 26, 45, 34,
                     50, 48, 61, 52, 73, 66};

        //创建三个块的对象
        Block b1 = new Block(21,0,5);
        Block b2 = new Block(45,6,11);
        Block b3 = new Block(73,12,17);

        //定义数组用来管理三个块的对象(索引表)
        Block[] blockArr = {b1,b2,b3};

        //定义一个变量用来记录要查找的元素
        int number = 37;

        //调用方法,传递索引表,数组,要查找的元素
        int index = getIndex(blockArr,arr,number);

        //打印一下
        System.out.println(index);



    }

    //利用分块查找的原理,查询number的索引
    private static int getIndex(Block[] blockArr, int[] arr, int number) {
        //1.确定number是在那一块当中
        int indexBlock = findIndexBlock(blockArr, number);

        if(indexBlock == -1){
            //表示number不在数组当中
            return -1;
        }

        //2.获取这一块的起始索引和结束索引   --- 30
        // Block b1 = new Block(21,0,5);   ----  0
        // Block b2 = new Block(45,6,11);  ----  1
        // Block b3 = new Block(73,12,17); ----  2
        int startIndex = blockArr[indexBlock].getStartIndex();
        int endIndex = blockArr[indexBlock].getEndIndex();

        //3.遍历
        for (int i = startIndex; i <= endIndex; i++) {
            if(arr[i] == number){
                return i;
            }
        }
        return -1;
    }


    //定义一个方法,用来确定number在哪一块当中
    public static int findIndexBlock(Block[] blockArr,int number){ //100


        //从0索引开始遍历blockArr,如果number小于max,那么就表示number是在这一块当中的
        for (int i = 0; i < blockArr.length; i++) {
            if(number <= blockArr[i].getMax()){
                return i;
            }
        }
        return -1;
    }



}

class Block{
    private int max;//最大值
    private int startIndex;//起始索引
    private int endIndex;//结束索引


    public Block() {
    }

    public Block(int max, int startIndex, int endIndex) {
        this.max = max;
        this.startIndex = startIndex;
        this.endIndex = endIndex;
    }

    /**
     * 获取
     * @return max
     */
    public int getMax() {
        return max;
    }

    /**
     * 设置
     * @param max
     */
    public void setMax(int max) {
        this.max = max;
    }

    /**
     * 获取
     * @return startIndex
     */
    public int getStartIndex() {
        return startIndex;
    }

    /**
     * 设置
     * @param startIndex
     */
    public void setStartIndex(int startIndex) {
        this.startIndex = startIndex;
    }

    /**
     * 获取
     * @return endIndex
     */
    public int getEndIndex() {
        return endIndex;
    }

    /**
     * 设置
     * @param endIndex
     */
    public void setEndIndex(int endIndex) {
        this.endIndex = endIndex;
    }

    public String toString() {
        return "Block{max = " + max + ", startIndex = " + startIndex + ", endIndex = " + endIndex + "}";
    }
}

扩展的分块查找(无规律的数据)

在这里插入图片描述
如上图所示,最小值“7”在中间,那么无论如何也无法向上面一样分块了。
我们只能退而求其次,让每一块无交集即可,如下图所示。
在这里插入图片描述
在这里插入图片描述

扩展的分块查找(查找的过程中还需要添加数据)

需求:在1~1000之间获取100个随机数,要求数据不重复。之前你每生成一个数据,就需要与已生成的(无顺序)数据进行比较,防止重复,效率很低。
改进方法,我把100个随机数分成10块,如下图所示:生成205时候只需要从第3块上查找是否重复即可。
在这里插入图片描述

  • 数组的0索引处存储1~100
  • 数组的1索引处存储101~200
  • 数组的2索引处存储201~300
  • 以此类推

但是实际上,我们一般不会采取这种方式,因为这种方式容易导致一块区域添加的元素过多,导致效率偏低。
更多的是先计算出当前数据的哈希值,用哈希值跟数组的长度进行计算,计算出应存入的位置,再挂在数组的后面形成链表,如果挂的元素太多而且数组长度过长,我们也会把链表转化为红黑树,进一步提高效率。

六、哈希查找 即上面的扩展

哈希查找是分块查找的进阶版,适用于数据一边添加一边查找的情况。
一般是数组 + 链表的结合体或者是数组+链表 + 红黑树的结合体。

七、树表查找 以后补充

标签:折半,arr,Java,int,mid,查找,return,public
From: https://blog.csdn.net/buyaotutou/article/details/140990737

相关文章

  • Java【案例2-5】 剪刀石头布小游戏
    案例介绍:“剪刀石头布”的游戏相信大家都不陌生,本案例要求编写一个剪刀石头布游戏的程序。程序启动后会随机生成1~3的随机数,分别代表剪刀、石头和布,玩家通过键盘输入剪刀、石头和布与电脑进行5轮的游戏,赢的次数多的一方为赢家。若五局皆为平局,则最终结果判为平局。案例思路: ......
  • Java【案例3-1】基于控制台的购书系统
    案例介绍:伴随互联网的蓬勃发展,网络购书系统作为电子商务的一种形式,正以其高效、低成本的优势逐步成为新兴的经营模式,人们已经不再满足互联网的用途仅仅局限于信息的浏览和发布,更渴望着能够充分享受互联网所带来的更多便利。网络购书系统正适应了当今社会快节奏地生活,使顾客足不......
  • 搭建Java集成开发环境教程
            对于Java开发,‌IntelliJIDEA是一个广泛使用的集成开发环境。‌它提供了卓越的代码自动补全、‌动态语法检测、‌重构功能,‌以及对各种主流框架和前沿技术的深度支持。‌IntelliJIDEA有Ultimate版和CommunityEdition版,‌Ultimate版功能全面但收费,‌而Communi......
  • Java异常处理-2
    throw关键字throw用来对外主动抛出一个异常,通常下面两种情况我们主动对外抛出异常:当程序遇到一个满足语法,但是不满足业务要求时,可以抛出一个异常告知调用者。程序执行遇到一个异常,但是该异常不应当在当前代码片段被解决时可以抛出给调用者。例packageexception;/**......
  • [Java并发]ThreadLocal补充
    ThreadLocal缺点及解决方案每个Thread上都有一个threadLocals属性,它是一个ThreadLocalMap,里面存放着一个Entry数组,key是ThreadLocal类型的弱引用,value是对用的值。所有的操作都是基于这个ThreadLocalMap操作的。但是它有一个局限性,就是不能在父子线程之间传递。即在子线程中无......
  • 2024年华为OD机试真题-求幸存数之和-(C++/Java/python)-OD统一考试(C卷D卷)
    2024华为OD机试真题目录-(B卷C卷D卷)-【C++JavaPython】_华为od机试csdn-CSDN博客 题目描述给一个正整数数列nums,一个跳数jump,及幸存数量left。运算过程为:从索引0的位置开始向后跳,中间跳过J个数字,命中索引为J+1的数字,该数被敲出,并从该点起跳,以此类推,直到幸存le......
  • Java基础语法:变量与数据类型
    变量1.概念:变量是用来存储数据的命名容器并在程序的不同部分使用它。2.语法:数据类型变量名称=初始值;可以这样理解:**数据类型:**鱼缸**变量名称:**鱼的名字**变量的值:**鱼缸里装的鱼或数量数量数据类型基本数据类型-整型:1.byte:8位,有符号整数(-128到127)2.short:......
  • IDEA发生“Error:java: 错误: 不支持发行版本 5”错误的解决方案
    1、问题描述如上图所示,使用IDEA创建了一个maven项目,在运行时发生“Error:java:错误:不支持发行版本5”的报错。原因分析:该错误是由于IDEA的各个配置项存在JDK版本冲突导致的。2、解决方案一2.1、设置Maven的JDK插件如上图所示,在pom.xml文件中,设置一个编译插......
  • [Java异常]OOM
    小伙伴们,有没有遇到过程序突然崩溃,然后抛出一个OutOfMemoryError的异常?这就是我们俗称的OOM,也就是内存溢出。简单来说,就是你的Java应用想要的内存超过了JVM愿意给的极限,就会抛出这个错误。那么为什么会出现OOM呢?一般都是由这些问题引起:分配过少:JVM初始化内存小,业务使用了大......
  • Java 基于微信小程序的学校心理咨询聊天室系统 uniapp毕业设计
    文末获取资源,收藏关注不迷路文章目录项目介绍功能需求技术介绍项目界面关键代码目录项目介绍该课题旨在创建一个专门针对大学生心理健康的知识科普平台,其受众包含大学生与其父母,包含知识科普,自我筛查,在线咨询,与匿名倾诉(包含父母与大学生)四个大点。全方位的对大学生......