七大查找算法
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);">/**<br> * @author 小也<br> * @create 2021/4/3 8:04<br> */<br>public class SequentialSearch {<br> public static void search(int[] arr,int x) {<br> boolean has = false;<br> for (int i : arr) {<br> if(i == x){<br> System.out.println("x存在");<br> has = true;<br> break;<br> }<br> }<br> if (!has) {<br> System.out.println("x不存在");<br> }<br> }<br>}<br></pre>
二分查询<br>
前提
数组必须有序
实现方式
递归
代码实现
<pre style="background-color: rgb(43, 43, 43); font-family: "JetBrains Mono", monospace; font-size: 9.8pt; color: rgb(169, 183, 198);">/**<br> * @author 小也<br> * @create 2021/4/3 8:09<br> */<br>public class BinarySearch {<br> public static void search(int[] arr,int left,int right,int x) {<br> if (x < arr[left] || x > arr[right]){<br> System.out.println("x不存在");<br> return;<br> }<br> int mid = left + (right - left)/2;<br> if (x == arr[mid]){<br> System.out.println("x存在");<br> }<br><br> if (x < arr[mid]){<br> search(arr,left,mid - 1,x);<br> }<br> if (x > arr[mid]){<br> search(arr,mid + 1,right,x);<br> }<br> }<br>}<br></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);<br></pre>
前提
数组必须有序
实现方式
递归
代码实现
<pre style="background-color: rgb(43, 43, 43); font-family: "JetBrains Mono", monospace; font-size: 9.8pt; color: rgb(169, 183, 198);">/**<br> * @author 小也<br> * @create 2021/4/3 8:32<br> */<br>public class InsertionSearch {<br> public static void search(int[] arr,int left,int right,int x) {<br> if (x < arr[left] || x > arr[right]){<br> System.out.println("x不存在");<br> return;<br> }<br> int mid = left + (x - arr[left])/(arr[right] - arr[left]) * (right - left);<br> if (x == arr[mid]){<br> System.out.println("x存在");<br> }<br><br> if (x < arr[mid]){<br> search(arr,left,mid - 1,x);<br> }<br> if (x > arr[mid]){<br> search(arr,mid + 1,right,x);<br> }<br> }<br>}<br></pre>
斐波那契查找
是二分查找的改进
<pre style="background-color: rgb(43, 43, 43); font-family: "JetBrains Mono", monospace; font-size: 9.8pt; color: rgb(169, 183, 198);">mid = low + fib[k - 1] - 1;<br></pre>
前提
数组必须有序
实现方式
⭐非递归
代码实现
<pre style="background-color: rgb(43, 43, 43); font-family: "JetBrains Mono", monospace; font-size: 9.8pt; color: rgb(169, 183, 198);">/**<br> * @author 小也<br> * @create 2021/4/3 9:10<br> */<br>public class FibonacciSearch {<br> /**<br> * Fibonacci数组最大长度<br> */<br> private static final int MAX_LENGTH = 20;<br> /**<br> * 构造一个Fibonacci数组<br> */<br> private static int[] fib(){<br> int[] fi = new int[MAX_LENGTH];<br> fi[0] = 1;<br> fi[1] = 1;<br> for (int i = 2; i < fi.length; i++){<br> fi[i] = fi[i - 1] + fi[i - 2];<br> }<br> return fi;<br> }<br> public static int search(int[] arr,int x) {<br> int low = 0;<br> int high = arr.length - 1;<br> int mid = 0;<br> int k = 0;<br> int[] fib = fib();<br> //找到略微大于等于x的那个分割点<br> while (high > fib[k] - 1){<br> k++;<br> }<br> //将数组扩容到F(k)-1<br> int[] temp = new int[fib[k]-1];<br> for(int i = 0; i < arr.length; i++){<br> temp[i] = arr[i];<br> }<br> //超过arr数组长度的位置填充arr的最后一个元素<br> for (int i = arr.length;i < fib[k]-1; i++){<br> temp[i] = arr[high];<br> }<br> while(low <= high){<br> mid = low + fib[k - 1] - 1;<br> if (x < temp[mid]){<br> high = mid - 1;<br> k--;<br> }else if(x > temp[mid]){<br> low = mid + 1;<br> k -= 2;<br> }else{<br> if (mid < high){<br> return mid;<br> }else{<br> return high;<br> }<br> }<br> }<br> return -1;<br> }<br>}<br></pre>
树表查找
从根节点开始查找
判断条件为当前节点非空
如果x<b><font color="#f15a23">小于</font></b>当前节点值，则把temp遍历节点替换成当前节点的<font color="#f15a23"><b>左孩子节点</b></font>
如果x<b><font color="#f15a23">大于</font></b>当前节点值，则把temp遍历节点替换成当前节点的<b><font color="#f15a23">右孩子节点</font></b>
分块查找
条件
第n块中的最小值要大于第n-1块的最大值
⭐块间有序，块内可以无序
需要一个索引表
实现思路
1、先在索引表中顺序查找（也可以二分查找）待查记录的所在块的位置
2、在块内顺序查找（只能顺序查找，因为块内可能无序）
哈希查找
通过hashcode计算hash值，找到数组下标，直接查询
哈希冲突
拉链法解决
开放定址法
往后找空位置
hashtable、hashmap就是根据哈希查找实现的
0 条评论
下一页
