Java 查找方法

桃扇骨 2024-03-26 11:35 109阅读 0赞

### 查找方法 ###

#### 基本查找（顺序查找） ####

package com.wang.search;
    
    import java.util.ArrayList;
    
    public class SearchDemo01 {
        
        public static void main (String[] args) {
        
            /**
             * 基本查找/顺序查找
             * 核心：从0索引开始，按个查找
             *
             * 需求：定义一个方法，利用基本查找，查询某个元素是否存在
             * 数据：{131,127,147,81,103,23,7,79}
             */
            int[] arr = {
        131,127,147,81,103,23,7,79,81};
            int number = 81;
    //        System.out.println (basicSerach (arr,number));
            basicSerach (arr,number);
    
        }
    
    /*    public static boolean basicSerach (int[] arr, int number) {
            //number在数组中是否存在
            for (int i = 0; i < arr.length; i++) {
                if (arr[i] == number) {
                    return true;
                }
            }
            return false;
        }*/
        //查找元素在数组中的索引
    public static void basicSerach (int[] arr, int number) {
        
        //number在数组中是否存在
        ArrayList<Integer> list = new ArrayList<> ();
        for (int i = 0; i < arr.length; i++) {
        
            if (arr[i] == number) {
        
               list.add (i);
            }
        }
        for (Integer i : list) {
        
            System.out.print (i+" ");
        }
    }
    
    }

### 二分查找（折半查找） ###

前提条件：数组中的数据必须是有序的
    核心逻辑：每次排除一半的查找范围

说明：元素必须是有序的，从小到大，或者从大到小都是可以的。

如果是无序的，也可以先进行排序。但是排序之后，会改变原有数据的顺序，查找出来元素位置跟原来的元素可能是不一样的，所以排序之后再查找只能判断当前数据是否在容器当中，返回的索引无实际的意义。

**基本思想**：也称为是折半查找，属于有序查找算法。用给定值先与中间结点比较。比较完之后有三种情况：

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

代码示例：

package com.itheima.search;
    
    public class A02_BinarySearchDemo1 {
        
        public static void main(String[] args) {
        
            //二分查找/折半查找
            //核心：
            //每次排除一半的查找范围
    
            //需求：定义一个方法利用二分查找，查询某个元素在数组中的索引
            //数据如下：{7, 23, 79, 81, 103, 127, 131, 147}
    
            int[] arr = {
        7, 23, 79, 81, 103, 127, 131, 147};
            System.out.println(binarySearch(arr, 150));
        }
    
        public static int binarySearch(int[] arr, int number){
        
            //1.定义两个变量记录要查找的范围
            int min = 0;
            int max = arr.length - 1;
    
            //2.利用循环不断的去找要查找的数据
            while(true){
        
                if(min > max){
        
                    return -1;
                }
                //3.找到min和max的中间位置
                int mid = (min + max) / 2;
                //4.拿着mid指向的元素跟要查找的元素进行比较
                if(arr[mid] > number){
        
                    //4.1 number在mid的左边
                    //min不变，max = mid - 1；
                    max = mid - 1;
                }else if(arr[mid] < number){
        
                    //4.2 number在mid的右边
                    //max不变，min = mid + 1;
                    min = mid + 1;
                }else{
        
                    //4.3 number跟mid指向的元素一样
                    //找到了
                    return mid;
                }
    
            }
        }
    }

### 3. 插值查找 ###

在介绍插值查找之前，先考虑一个问题：
    
    	为什么二分查找算法一定要是折半，而不是折四分之一或者折更多呢？
    
    其实就是因为方便，简单，但是如果我能在二分查找的基础上，让中间的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的计算方式即可。

### 4. 斐波那契查找 ###

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

![img][]

基本思想：也是二分查找的一种提升算法，
    通过运用黄金比例的概念在数列中选择查找点进行查找，提高查找效率。
    同样地，斐波那契查找也属于一种有序查找算法。
    
    斐波那契查找也是在二分查找的基础上进行了优化，优化中间点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;
        }
    }

### 5. 分块查找 ###

当数据表中的数据元素很多时，可以采用分块查找。
    
    汲取了顺序查找和折半查找各自的优点，既有动态结构，又适于快速查找
    
    分块查找适用于数据较多，但是数据不会发生变化的情况，如果需要一边添加一边查找，建议使用哈希查找
    
    分块查找的过程：
    
    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 + "}";
        }
    }

### 6. 哈希查找 ###

哈希查找是分块查找的进阶版，适用于数据一边添加一边查找的情况。
    
    一般是数组 + 链表的结合体或者是数组+链表 + 红黑树的结合体
    
    在课程中，为了让大家方便理解，所以规定：
    
    - 数组的0索引处存储1~100
    - 数组的1索引处存储101~200
    - 数组的2索引处存储201~300
    - 以此类推
    
    但是实际上，我们一般不会采取这种方式，因为这种方式容易导致一块区域添加的元素过多，导致效率偏低。
    
    更多的是先计算出当前数据的哈希值，用哈希值跟数组的长度进行计算，计算出应存入的位置，再挂在数组的后面形成链表，如果挂的元素太多而且数组长度过长，我们也会把链表转化为红黑树，进一步提高效率。

### 7. 树表查找 ###

本知识点涉及到数据结构：树。
    
    建议先看一下后面阿玮讲解的数据结构，再回头理解。
    
    基本思想：二叉查找树是先对待查找的数据进行生成树，确保树的左分支的值小于右分支的值，然后在就行和每个节点的父节点比较大小，查找最适合的范围。 这个算法的查找效率很高，但是如果使用这种查找方法要首先创建树。 
    
    　　二叉查找树（BinarySearch Tree，也叫二叉搜索树，或称二叉排序树Binary Sort Tree），具有下列性质的二叉树：
    
    　　1）若任意节点左子树上所有的数据，均小于本身；
    
    　　2）若任意节点右子树上所有的数据，均大于本身；
    
    　　二叉查找树性质：对二叉查找树进行中序遍历，即可得到有序的数列。
    
    
    　　基于二叉查找树进行优化，进而可以得到其他的树表查找算法，如平衡树、红黑树等高效算法。
    
    具体细节大家可以参见B站阿玮讲解课程：从入门到起飞。在集合章节详细讲解了树数据结构。全程采取动画形式讲解，让大家一目了然。
    
    在此不多做阐述。
    
    	不管是二叉查找树，还是平衡二叉树，还是红黑树，查找的性能都比较高

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

[img]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/e7fca9f605544fdd88cabaea1ff7fc79.png
[c4688cb36eb746e2b49e7f43ba3e7157.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/c3042738e4dc40fca36430adfb8ae230.png