当前位置：首页 > news >正文

七大查找算法详解并附代码实现

news 来源：原创 2024/5/9 1:03:59

基本查找

也叫做顺序查找

说明：顺序查找适合于存储结构为数组或者链表。

基本思想：顺序查找也称为线形查找，属于无序查找算法。从数据结构线的一端开始，顺序扫描，依次将遍历到的结点与要查找的值相比较，若相等则表示查找成功；若遍历结束仍没有找到相同的，表示查找失败。

示例代码：

public class A01_BasicSearchDemo1 {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};int number = 81;System.out.println(basicSearch(arr,number));}//参数：//一：数组//二：要查找的元素//返回值：//元素是否存在public static boolean basicSearch(int[]arr, int number){//利用基本查找来查找number在数组中是否存在for(int i = 0; i < arr.length; i++){if(arr[i] == number){return true;}}return false;}

二分查找

也叫做折半查找

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

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

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

相等

说明找到了
要查找的数据比中间节点小

说明要查找的数字在中间节点左边
要查找的数据比中间节点大

说明要查找的数字在中间节点右边

代码示例：

public class BinarySearchTest {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, 131));}private 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;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;}}}}

插值查找

在介绍插值查找之前，先考虑一个问题：

为什么二分查找算法一定要是折半，而不是折四分之一或者折更多呢？

其实就是因为方便，简单，但是如果我能在二分查找的基础上，让中间的mid点，尽可能靠近想要查找的元素，那不就能提高查找的效率了吗？

二分查找中查找点计算如下：

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

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

Mid = Begin + ( (End - Begin) / (A[End] - A[Begin]) ) * (X - A[Begin])

式子中，各部分的含义分别是：

Mid：计算得出的元素的位置；

End：搜索区域内最后一个元素所在的位置；

Begin：搜索区域内第一个元素所在的位置；

X：要查找的目标元素；

A[]：表示整个待搜索序列。

为了方便讲解，我们仍将 Mid 位置上的元素称为 “中间元素”。

使用插值查找算法在 {1,2,3,4,5,6,7,8,9,10} 升序序列中查找元素 2，查找过程如下：

假设序列中各个元素的位置为 0~9，搜索区域为整个序列，通过公式计算出 “中间元素” 的位置：

Mid = 0 + ( (9-0)/(10-1) ) * (2-1) = 1

“中间元素” 的位置为 1，也就是元素 2，显然这是我们要找的目标元素，查找结束。整个查找过程如下所示：

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

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

细节：对于表长较大，而关键字分布又比较均匀的查找表来说，插值查找算法的平均性能比折半查找要好的多。反之，数组中如果分布非常不均匀，那么插值查找未必是很合适的选择。

代码跟二分查找类似，只要修改一下mid的计算方式即可。

public class InterpolationSearchTest {public static void main(String[] args) {//二分查找/折半查找//核心：//每次排除一半的查找范围//需求：定义一个方法利用二分查找，查询某个元素在数组中的索引//数据如下：{7, 23, 79, 81, 103, 127, 131, 147}int[] arr = {1, 2, 3, 4, 5, 6, 7, 8};System.out.println(InterpolationSearch(arr, 8));}private static int InterpolationSearch(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 - min) / (arr[max] - arr[min]) * (number - arr[min]));;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;}}}
}

斐波那契查找

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

　　黄金比例又称黄金分割，是指事物各部分间一定的数学比例关系，即将整体一分为二，较大部分与较小部分之比等于整体与较大部分之比，其比值约为1:0.618或1.618:1。

　　0.618被公认为最具有审美意义的比例数字，这个数值的作用不仅仅体现在诸如绘画、雕塑、音乐、建筑等艺术领域，而且在管理、工程设计等方面也有着不可忽视的作用。因此被称为黄金分割。

　　在数学中有一个非常有名的数学规律：斐波那契数列：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89…….

（从第三个数开始，后边每一个数都是前两个数的和）。

然后我们会发现，随着斐波那契数列的递增，前后两个数的比值会越来越接近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:前一块中的最大数据,小于后一块中所有的数据(块内无序,块间有序)
块数数量一般等于数字的个数开根号
核心思路:先确定要查找的元素在那一块儿,然后在块内挨个查找

分块查找的过程：

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

代码示例：

public class BlockingSearch {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};//1.把数据进行分块//创建三个块的对象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 = 32;//调用方法,传递索引表,数组,要查找的元素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) {return -1;}//获取这一块的起始索引和结束索引int startIndex = blockArr[indexBlock].getStartIndex();int endIndex = blockArr[indexBlock].getEndIndex();for (int i = startIndex; i <= endIndex; i++) {if (arr[i] == number) {return i;}}return -1;}//定义一个方法,用来确定number在那一块中public static int findIndexBlock(Block[] blockArr, int number) {/* Block b1 = new Block(21, 0, 5); ---0Block b2 = new Block(45, 6, 11); ---1Block b3 = new Block(73, 12, 17);---2 *///从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 + "}";}
}

//无序
int[] arr = {27, 22, 30, 40, 36,13, 19, 16, 20,7,10,43, 50, 48};

 //定义一个方法,用来确定number在那一块中public static int findIndexBlock(Block1[] blockArr, int number) {/* Block1 b1 = new Block1(40,22, 0, 4);Block1 b2 = new Block1(20, 13, 5,8);Block1 b3 = new Block1(10, 7, 9,10);Block1 b4 = new Block1(50, 43, 11,13);*///从0索引开始遍历blockArr,如果number小于max,大于min,那么就表示number是这一块当中的for (int i = 0; i < blockArr.length; i++) {if (number <= blockArr[i].getMax() && number > blockArr[i].getMin()) {return i;}}return -1;}