七大查找算法

2021-04-03 15:50:53   12  举报





AI智能生成

请大家不要直接克隆，着手梳理一遍才会变成自己的知识

查找算法

二分查找

斐波那契

模版推荐

作者其他创作

大纲/内容

顺序查找

实现方式

数组遍历

代码实现

<pre style="background-color: rgb(43, 43, 43); font-family: "JetBrains Mono", monospace; font-size: 9.8pt; color: rgb(169, 183, 198);">/** * @author 小也 * @create 2021/4/3 8:04 */ public class SequentialSearch { public static void search(int[] arr,int x) { boolean has = false; for (int i : arr) { if(i == x){ System.out.println("x存在"); has = true; break; } } if (!has) { System.out.println("x不存在"); } } } </pre>

二分查询

前提

数组必须有序

实现方式

递归

代码实现

<pre style="background-color: rgb(43, 43, 43); font-family: "JetBrains Mono", monospace; font-size: 9.8pt; color: rgb(169, 183, 198);">/** * @author 小也 * @create 2021/4/3 8:09 */ public class BinarySearch { public static void search(int[] arr,int left,int right,int x) { if (x < arr[left] || x > arr[right]){ System.out.println("x不存在"); return; } int mid = left + (right - left)/2; if (x == arr[mid]){ System.out.println("x存在"); } if (x < arr[mid]){ search(arr,left,mid - 1,x); } if (x > arr[mid]){ search(arr,mid + 1,right,x); } } } </pre>

插值查找

是二分查找的改进

<pre style="background-color: rgb(43, 43, 43); font-family: "JetBrains Mono", monospace; font-size: 9.8pt; color: rgb(169, 183, 198);">int mid = low+(value-a[low])/(a[high]-a[low])*(high-low); </pre>

前提

数组必须有序

实现方式

递归

代码实现

<pre style="background-color: rgb(43, 43, 43); font-family: "JetBrains Mono", monospace; font-size: 9.8pt; color: rgb(169, 183, 198);">/** * @author 小也 * @create 2021/4/3 8:32 */ public class InsertionSearch { public static void search(int[] arr,int left,int right,int x) { if (x < arr[left] || x > arr[right]){ System.out.println("x不存在"); return; } int mid = left + (x - arr[left])/(arr[right] - arr[left]) * (right - left); if (x == arr[mid]){ System.out.println("x存在"); } if (x < arr[mid]){ search(arr,left,mid - 1,x); } if (x > arr[mid]){ search(arr,mid + 1,right,x); } } } </pre>

斐波那契查找

是二分查找的改进

前提

数组必须有序

实现方式

⭐非递归

代码实现

<pre style="background-color: rgb(43, 43, 43); font-family: "JetBrains Mono", monospace; font-size: 9.8pt; color: rgb(169, 183, 198);">/** * @author 小也 * @create 2021/4/3 9:10 */ public class FibonacciSearch { /** * Fibonacci数组最大长度 */ private static final int MAX_LENGTH = 20; /** * 构造一个Fibonacci数组 */ private static int[] fib(){ int[] fi = new int[MAX_LENGTH]; fi[0] = 1; fi[1] = 1; for (int i = 2; i < fi.length; i++){ fi[i] = fi[i - 1] + fi[i - 2]; } return fi; } public static int search(int[] arr,int x) { int low = 0; int high = arr.length - 1; int mid = 0; int k = 0; int[] fib = fib(); //找到略微大于等于x的那个分割点 while (high > fib[k] - 1){ k++; } //将数组扩容到F(k)-1 int[] temp = new int[fib[k]-1]; for(int i = 0; i < arr.length; i++){ temp[i] = arr[i]; } //超过arr数组长度的位置填充arr的最后一个元素 for (int i = arr.length;i < fib[k]-1; i++){ temp[i] = arr[high]; } while(low <= high){ mid = low + fib[k - 1] - 1; if (x < temp[mid]){ high = mid - 1; k--; }else if(x > temp[mid]){ low = mid + 1; k -= 2; }else{ if (mid < high){ return mid; }else{ return high; } } } return -1; } } </pre>

树表查找

从根节点开始查找

判断条件为当前节点非空

如果x小于当前节点值，则把temp遍历节点替换成当前节点的左孩子节点

如果x大于当前节点值，则把temp遍历节点替换成当前节点的右孩子节点

分块查找

条件

第n块中的最小值要大于第n-1块的最大值

⭐块间有序，块内可以无序

需要一个索引表

实现思路

1、先在索引表中顺序查找（也可以二分查找）待查记录的所在块的位置