深圳住房建设局网站申报,做公司网站的公司有哪些,wordpress jetpack 慢,怎么开始做网站查找算法
常用查找算法
1,顺序(线性)查找
2,二分查找/折半查找
3,插值查找
4,斐波那契查找
线性查找
线性查找,通过遍历和逐一比对,在发现相同值时返回下标
代码如下
public int Seqsearch(int t, int[] arr) {for (int i 0; i arr.length; i) {if (t arr[i]) …查找算法
常用查找算法
1,顺序(线性)查找
2,二分查找/折半查找
3,插值查找
4,斐波那契查找
线性查找
线性查找,通过遍历和逐一比对,在发现相同值时返回下标
代码如下
public int Seqsearch(int t, int[] arr) {for (int i 0; i arr.length; i) {if (t arr[i]) {return i;}}return -1;
}二分查找
只能对有序数组查找
使用递归进行二分查找
1,确定数组中间的下标
2,让需要查找的数字与mid进行比较,递归向左或者右进行查找
3,得到结果
代码如下
public int binarysearch(int t,int left,int right,int[] arr){int mid (leftright)/2;if(leftright){return -1;}if(arr[mid]t){return mid;}else if(arr[mid]t){return binarysearch(t,left,mid-1,arr);//递归最终返回mid}else{return binarysearch(t,mid1,right,arr);//递归最终返回mid}
}升级二分查找
找到数组所有的符合条件元素(相同元素全部返回)
在找到元素后向其左右扫描,直到扫完全部相同元素,放入一个集合中
最后返回一个集合
插值查找
类似于二分查找,但插值查找每次从自适应mid处开始查找
插值索引公式:mid low(high-low)*(key-arr[low])/(arr[high]-arr[low])
即每次重新查找会根据上一次的mid值与所求值的差值大小占整个查找范围差值大小的比值进行查找
在分布均匀的数组中较为优势
eg:在一个0-100的数组中查找值,可以直接一次找到
代码如下
public int insertsearch(int t,int left,int right,int[] arr){if(tright || tleft){return -1;}int mid left(right-left)*(t-arr[left])/(arr[right]-arr[left]);if(leftright){return -1;}if(arr[mid]t){return mid;}else if(arr[mid]t){return insertsearch(t,left,mid-1,arr);}else{return insertsearch(t,mid1,right,arr);}}在不均匀的数据结构中,这个查找方法不一定有优势
斐波那契查找算法
斐波那契数列元素之间的比例无限接近于黄金分割值0.618
查找思路
原理来自于斐波那契数列中后项等于前两项的和
所以只要当数列长度等于斐波那契数列中的某一项,就可以按照斐波那契数列的比例无限分割,直到1为止
mid low F(k-1)-1
F代表斐波那契数列
将分割点放在黄金分割点附近
当数据结构长度不足斐波那契数列中某个元素的值时,需要进行补长
代码如下
// 辅助函数生成斐波那契数列
private static int[] generateFibonacci(int n) {int[] fibonacci new int[n];fibonacci[0] 0;fibonacci[1] 1;for (int i 2; i n; i) {fibonacci[i] fibonacci[i - 1] fibonacci[i - 2];}return fibonacci;
}// 斐波那契查找算法
public static int fibonacciSearch(int[] arr, int key) {int n arr.length;// 生成斐波那契数列找到最接近且大于等于 n 的值int[] fibonacci generateFibonacci(n);int k 0;while (fibonacci[k] n) {k;}// 将数组扩展到斐波那契数列的长度int[] temp new int[fibonacci[k]];System.arraycopy(arr, 0, temp, 0, n);int low 0;int high n - 1;// 主要查找过程while (low high) {int mid low fibonacci[k - 1] - 1;if (key temp[mid]) {high mid - 1;k - 1;} else if (key temp[mid]) {low mid 1;k - 2;} else {// 找到了目标元素需要判断返回的是原数组中的索引还是扩展数组中的索引return Math.min(mid, high);}}// 未找到目标元素return -1;
}public static void main(String[] args) {int[] arr {1, 3, 5, 7, 9, 11, 13, 15};int key 7;int result fibonacciSearch(arr, key);if (result ! -1) {System.out.println(元素 key 在数组中的索引为 result);} else {System.out.println(元素 key 不在数组中);}
}
