查找算法----二分查找、插值查找、斐波那契查找
1、二分查找
二分查找的思路分析
-
先确定该数组的中间的下标mid = (left+right)/2
-
然后让需要查找的数findVal和arr[mid]比较
2.1 findVal > arr[mid]，说明你要查找的数在md的右边，因此需要递归的向右查找
2.2 findVal < arr【mid】，说明你要查找的数在mid的左边，因此需要递归的向左查找
2.3 findval arr（mid】说明找到，就返回
-
什么时候我们需要结束递归，
1）找到就信束递归
2）递归完整个数组，仍然没有找到ndVal，也需要结束递归left > right就退出
2、二分查找代码实现
package com.yishuai.find;
/**
* @AuThor yishuai
* @description 二分查找法(只能运用在有序的数组等)
* @date 2021/3/24 3:20 下午
*/
public class TwoSearcher {
public static void main(String[] args) {
int[] initial ={1,2,3,4,5,6,7,8,9};
int i = twoSearcher(initial, 0, initial.length - 1, 2);
System.out.println(i);
}
/**
* 二分查找
* @Param initial 初始数组
* @param left 左边的索引
* @param right 右边的索引
* @param findVal 被查找的值
* @return
*/
public static int twoSearcher(int[] initial,int left,int right,int findVal){
//当左边的索引已经大于右边了,或者小于数组的最小数，大于数组的最大数，代表找不到了
//左右的索引可以相等，代表只剩下了这一个数
if (left > right || findVal < initial[0] || findVal > initial[initial.length - 1]){
return -1;
}
int mid = (left+right)/2;
if (initial[mid] < findVal){
return twoSearcher(initial,mid + 1,right,findVal);
}else if (initial[mid] > findVal){
return twoSearcher(initial,left,mid - 1,findVal);
}else {
return mid;
}
}
}
3、插值查找(自适应查找)
插值查找思路分析
1) 插值查找原理介绍:
插值查找算法类似于二分查找，不同的是插值查找每次从自适应 mid 处开始查找。
2) 将折半查找中的求 mid 索引的公式 , left 表示左边索引, right 表示右边索引， findVal代表被查找的值
3）公式 int mid = left + (right – left) * (findVal – arr[left]) / (arr[right] – arr[left])
4、插值查找代码实现
package com.yishuai.find;
/**
* @author yishuai
* @description 插值查找(自适应查找)
* @date 2021/3/24 4:23 下午
*/
public class InsertSearcher {
public static void main(String[] args) {
int[] initial = {1, 2, 3, 4, 5, 6, 7, 8, 9};
int i = insertSearcher(initial, 0, initial.length - 1, 2);
System.out.println(i);
}
/**
* 插值查找(自适应查找)
* @param initial 初始数组
* @param left 左边的索引
* @param right 右边的索引
* @param findVal 被查找的值
* @return
*/
private static int insertSearcher(int[] initial, int left, int right, int findVal) {
if (left > right || findVal < initial[0] || findVal > initial[initial.length - 1]){
return -1;
}
//插值查找的特定公式，其他的和二分查找一样
int mid = left + (right-left) * (findVal - initial[left])/(initial[right] - initial[left]);
if (initial[mid] < findVal){
return insertSearcher(initial,mid + 1,right,findVal);
}else if(initial[mid] > findVal){
return insertSearcher(initial,left,mid - 1,findVal);
}else {
return mid;
}
}
}
5、插值查找注意实现
1) 对于数据量较大，关键字分布比较均匀的查找表来说，采用插值查找, 速度较快.
2) 关键字分布不均匀的情况下，该方法不一定比折半查找要好
6、斐波那契查找(黄金分割法)
有前面两个就够了，感觉用不到这个算法。略，哈哈哈
[复制链接]
发表于 2021-3-24 17:09
|
发表于 2021-4-29 17:50
