第九章 顺序查找、二分查找、插值查找和斐波那契查找

文章目录

第九章 顺序查找、二分查找、插值查找和斐波那契查找一、顺序查找1.基本介绍2.代码实现二、二分查找1.基本介绍2.代码实现三、插值查找1.基本介绍2.代码实现四、斐波那契查找1.基本介绍2.原理分析3.代码实现

一、顺序查找

1.基本介绍

顺序查找又称线性查找，其基本思想是：遍历数组，返回下标

2.代码实现

package com.sisyphus.search;/*** @Description: 顺序查找$* @Param: $* @return: $* @Author: Sisyphus* @Date: 7/19$*/public class SequenceSearch {public static void main(String[] args) {int[] arr = {1, 9, 11, -1, 34, 89};int index = sequenceSearch(arr,11);if (index == -1){System.out.println("没有查找到 " + index);}else{System.out.println("下标为：" + index);}}/***这里我们实现的顺序查找是找到一个满足条件的值就返回* @param arr* @param value* @return*/public static int sequenceSearch(int[] arr, int value){//顺序查找时逐一比对，发现有相同值，就返回下标for (int i = 0; i < arr.length; i++) {if (arr[i] == value){return i;}}return -1;}}

二、二分查找

1.基本介绍

二分查找又叫折半查找，首先二分查找的数组是要有序的，如果无序就不能用二分查找

算法步骤：

首先确定该数组的中间下标 mid = （left + right）/ 2然后让 arr[mid] 和要和查找的元素比较，如果要查找的元素更大，说明应该向右查找，反之向左将左(右)边当成一个新数组，重复第一第二步，找到了就结束递归，或者遍历完了数组也没找到也结束递归

2.代码实现

package com.sisyphus.search;import java.util.ArrayList;import java.util.List;/*** @Description: 二分查找$* @Param: $* @return: $* @Author: Sisyphus* @Date: 7/20$*/public class BinarySearch {public static void main(String[] args) {int arr[] = {1, 8, 10, 89, 1000, 1000, 1000, 1000, 1234};List<Integer> resIndexList = binarySearch2(arr, 0, arr.length -1, 1000);System.out.println("resIndexList=" + resIndexList);}//二分查找算法/**** @param arr 数组* @param left 左边的索引* @param right 右边的索引* @param findVal 要查找的值* @return 如果找到就返回下标，如果没有找到，就返回 -1*/public static int binarySearch(int[] arr, int left, int right, int findVal){//当 left > right 时，说明遍历整个数组也没找到if (left > right || findVal < arr[0] || findVal > arr[arr.length - 1]){return -1;}int mid = (left + right) / 2;int midVal = arr[mid];if (findVal > midVal){//向右递归return binarySearch(arr, mid + 1, right, findVal);}else if (findVal < midVal){//向左递归return binarySearch(arr, left, mid - 1,findVal);}else{return mid;}}/*** 假设有多个值等于要查找的值，返回所有这些值的索引* 思路：* 1。找到 mid 索引值后，不返回* 2。向 mid 索引值的左边扫描，将所有满足 1000 的元素的下标加入到集合 ArrayList* 3。向 mid 索引值的右边扫描，将所有满足 1000 的元素的下标加入到集合 ArrayList* 4。将 Arraylist 返回* @param arr* @param left* @param right* @param findVal* @return*/public static List<Integer> binarySearch2(int[] arr, int left, int right, int findVal){//当 left > right 时，说明遍历整个数组也没找到if if (left > right || findVal < arr[0] || findVal > arr[arr.length - 1]){return new ArrayList<Integer>();}int mid = (left + right) / 2;int midVal = arr[mid];if (findVal > midVal){//向右递归return binarySearch2(arr, mid + 1, right, findVal);}else if (findVal < midVal){//向左递归return binarySearch2(arr, left, mid - 1,findVal);}else{List<Integer> resIndexlist = new ArrayList<>();int temp = mid - 1;while(true){if ((temp < 0) || (arr[temp] != findVal)){//退出break;}//否则就把 temp 放入 resIndexlistresIndexlist.add(temp);temp--;//temp 左移}resIndexlist.add(mid);temp = mid + 1;while(true){if ((temp > arr.length - 1) || arr[temp] != findVal){//退出break;}//否则就把 temp 放入 resIndexlistresIndexlist.add(temp);temp++;//temp 右移}return resIndexlist;}}}

三、插值查找

1.基本介绍

插值查找也是二分查找，不同的是，mid的计算公式不再是mid = (left + right) / 2，变成了mid = left + (findVal - arr[left]) / (arr[right] - arr[left]) * (right - left)，其他的都和二分查找一样

举个例子：

数组 arr = [1,2,3,……，100]

我们需要查找的值是 1

如果采用二分查找，我们需要很多次递归

如果使用插值查找

mid = 0 + (1 - 1) / (100 - 1) × (99 - 0) = 0

与二分查找对比：

对于数据量较大，关键字分布比较均匀的查找表来说，采用插值查找，速度较快关键字分布不均匀的情况下，该方法不一定比二分查找好必须先判断（findVal < arr[0] || findVal > arr[arr.length - 1 ），防止越界

2.代码实现

package com.sisyphus.search;import java.util.Arrays;/*** @Description: 插值查找$* @Param: $* @return: $* @Author: Sisyphus* @Date: 7/20$*/public class InsertValueSearch {public static void main(String[] args) {int[] arr = new int[100];for (int i = 0; i < 100; i++) {arr[i] = i + 1;}System.out.println(Arrays.toString(arr));int index = insertValueSearch(arr, 0, arr.length - 1, 1);System.out.println("index=" + index);}public static int insertValueSearch(int[] arr,int left, int right, int findVal){//当 left > right 时，说明遍历整个数组也没找到//findVal < arr[0] || findVal > arr[arr.length - 1 防止越界if (left > right || findVal < arr[0] || findVal > arr[arr.length - 1]){return -1;}int mid = (left + right) / 2;int midVal = arr[mid];if (findVal > midVal){//向右递归return insertValueSearch(arr, mid + 1, right, findVal);}else if (findVal < midVal){//向左递归return insertValueSearch(arr, left, mid - 1,findVal);}else{return mid;}}}

四、斐波那契查找

1.基本介绍

斐波那契查找和二分查找、插值查找类似，数组也要是有序的。不同之处还是 mid 的计算方法。公式为：mid = left + F(k-1) - 1

二分查找需要进行除法，插值查找需要进行更复杂的乘法和除法，而斐波那契查找只需要使用加法和减法，在数据量较大时优势更明显

2.原理分析

斐波那契查找的整个过程可以分为：

构建斐波那契数列计算数组长度对应的斐波那契数列元素个数对数组进行填充循环进行区间分割，查找中间值判断中间值和目标值的关系，确定更新策略

构建斐波那契数列如下：

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]

假设有如下数据：

[1, 2, 4, 6, 7, 9, 13,

16, 17, 21, 23, 25, 27,

31, 45, 56, 58, 61, 65,

67, 73, 75, 88, 93, 102]

上述数据共 25 个元素，不对应斐波那契数列中的任何一个 F(n)。此时，策略是采用 “大于数组长度的最近的一个斐波那契数值” 。比如当前数组长度为 25，斐波那契数列中大于 25 的最近元素为 34

确定了斐波那契数值后，就要进行数值填充，即将数组从 25 个元素填充到 34 个。填充时，将第 26 到 34 个元素的值设置为第 25 个元素的值，即最大值填充

接着就循环进行区间分割，查找中间值。这个步骤与前面介绍的二分查找和插值查找相似，都是不断地缩小搜索区间，进而确定目标值的位置。每次分割中间位置的计算为：mid = left + F(k - 1) - 1

此时数组被分割为左右两个区间，左边区间含有 F(k - 1) 个元素，mid 减一是因为下标从 0 开始。例：F(4) 有 3 个元素，分割后左边有 2个元素，右边有 1 个元素

然后判断中间值和目标值的关系，确定更新策略

中间值和目标值有三种大小关系，分别对应三种处理方式：

相等，查找成功，返回中间位置中间值小于目标值，则说明目标值位于右区间，右区间含有 F(k - 2) 个元素，所以 k 应该更新为 k - 2中间值大于目标值，则说明目标值位于左区间，左区间含有 F(k - 1) 个元素，所以 k 应该更新为 k - 1

3.代码实现

package com.sisyphus.search;import java.util.Arrays;/*** @Description: 斐波那契查找$* @Param: $* @return: $* @Author: Sisyphus* @Date: 7/20$*/public class FibonacciSearch {public static int maxSize = 20;public static void main(String[] args) {int[] arr = {1, 8, 10, 89, 1000, 1234};System.out.println("index=" + fibonacciSearch(arr,89));}//因为后面我们 mid = left + F(k -1) - 1，需要使用到斐波那契数列，因此我们需要先获取到一个斐波那契数列//非递归方法得到一个斐波那契数列public static int[] fib(){int[] f = new int[maxSize];f[0] = 1;f[1] = 1;for (int i = 2; i < maxSize; i++) {f[i] = f[i - 1] + f[i - 2];}return f;}//编写斐波那契查找算法/**** @param arr 数组* @param findVal 我们需要查找的值* @return返回对应的下标，如果没有返回 -1*/public static int fibonacciSearch(int[] arr, int findVal){int left = 0;int right = arr.length - 1;int k = 0;//表示斐波那契分割数值的下标int mid = 0;//存放 mid 值int f[] = fib();//获取斐波那契数列//获取到斐波那契分割数值的下标while(right > f[k] - 1){k++;}//因为 f[k] 的值可能大于 a 的长度，因此我们需要使用 Arrays 类，构造一个新的数组，并指向 a[]//不足的部分会使用 0 填充int[] temp = Arrays.copyOf(arr,f[k]);//实际上需要使用 arr 数组最后的数填充 temp//for 循环中发生了如下变化//temp = {1,8,10,89,1000,1234,0,0,0} => temp = {1,8,10,89,1000,1234,1234,1234,1234}for (int i = right + 1; i < temp.length; i++) {temp[i] = arr[right];}//使用 while 来循环处理，找到我们的数 findValwhile(left <= right){//只要满足这个条件，就可以进行查找mid = left + f[k - 1] - 1;if (findVal < temp[mid]){//我们应该继续向数组的左边查找right = mid - 1;//1.全部元素 = 左边元素 + 右边元素//2.f[k] = f[k - 1] + f[k - 2]//因为左边有 f[k - 1] 个元素，所以可以继续拆分 f[k - 1] = f[k - 2] + f[k - 3]//即在 f[k - 1] 的左边继续查找 k--//即下次循环 mid = f[k - 1 - 1] - 1k--;}else if (findVal > temp[mid]){//我们应该继续向数组的右边查找left = mid + 1;//1、全部元素 = 左边元素 + 右边元素//2.f[k] = f[k - 1] + f[k - 2]//因为右边有 f[k - 2] 个元素，所以继续拆分 f[k - 1] = f[k - 3] + f[k - 4]//即在 f[k - 2] 的左边继续查找 k-= 2//即下次循环 mid = f[k - 1 - 2] -1k -= 2;}else{//找到了if (mid <= right){return mid;}else{return right;}}}return -1;}}