插值查找原理介绍:
1)插值查找算法类似于二分查找,不同的是插值查找每次从自适应mid处开始查找
2)将折半查找中的求mid 索引的公式, low表示左边索引, high表示右边索引.
3)int midindex =low + (high-low) * (key - arr(low) / (arr[high]-arr[low); /"插值索引*/
4)举例说明插值查找算法1-100的数组
-
package com.alibaba.search;
-
-
public
class InsertValueSearch {
-
public static void main(String[] args) {
-
int[] arr=
new
int[
100];
-
for (
int i =
0; i < arr.length; i++) {
-
arr[i]=i+
1;
-
}
-
int index = insertValueSearch(arr,
0, arr.length-
1,
5);
-
System.out.println(index);
-
}
-
//插值算法方法
-
public static int insertValueSearch(int arr[],int left,int right,int findVal){
-
System.out.println(
"插值查找的次数···");
-
//优化 防止mid 越界
-
if (left>right||arr[
0]>findVal||findVal>arr[arr.length-
1]){
-
return -
1;
-
}
-
//请mid
-
int mid=left+(right-left)*(findVal-arr[left])/(arr[right]-arr[left]);
-
int midVal=arr[mid];
-
if (findVal>midVal){
//说明应该向右递归
-
return insertValueSearch(arr,mid+
1,right,findVal);
-
}
else
if (findVal<midVal){
-
return insertValueSearch(arr,
0,mid-
1,findVal);
-
}
else{
-
return mid;
-
}
-
}
-
}
插值查找的注意事项：
1)对于数据量较大,关键字分布较均匀的查找表来说,采用插值查找速度快
2)关键字分布不均匀的情况下,该方法不一定比折半查找要好
斐波那契(黄金分割算法)查找基本介绍:
1)黄金分割点是指把一条线段分割为两部分,使其中一部分与全长之比等于另一部分与这部分之比,取其前三位数字的近似值,是0.618,由于按此比例设计的造型十分美丽,因此称为黄金分割,也称为中外比,这是一个神奇的数字,会带来意想不到的效果。
2)斐波那契数列{1,1,2,3,5,8,13,21,34,55}发现斐波那契数列的两个相邻数的比例，无限接近黄金比例0.618
斐波那契(黄金分割算法)原理:
斐波那契查找原理与前两种相似,仅仅改变了中间节点(mid)的位置,mid不再是中间或插值得到,而是位于黄金分割点附近,即mid=low+F(k-1)-1 (F代表斐波那契数列),如下图所示:
对F[k-1]-1的理解：
1) 由斐波那契数列F[k]=F[k-1]+ F[k-2]的性质,可以得到(F[k]-1)= (F[k-1]-1) +(F[k-2]-1) +1.该式说明:只要顺序表的长度为F[k]-1,则可以将该表分成长度为F[k-1]-1和F[k-2]-1的两段,即如上图所示。从而中间位置为mid=low+F(k-1)-1
2)类似的,每一子段也可以用相同的方式分割
3)但顺序表长度n不一定刚好等于F[k]-1,所以需要将原来的顺序表长度n增加至F[k]-1.这里的k值只要能使得F[k]-1恰好大于或等于n即可,由以下代码得到,顺序表长度增加后,新增的位置(从n+1到F[k]-1位置),都赋为n位置的值即可
斐波那契查找应用案例：
请对一个有序数组进行斐波那契查找{1,8, 10, 89, 1000, 1234} ,输入一个数看看该数组是否存在此数,并且求出下标,如果没有就提示“没有这个数“。
代码实现：
-
package com.alibaba.search;
-
-
import java.util.Arrays;
-
-
public
class FibonacciSearch {
-
public
static
int maxSize=
20;
-
public static void main(String[] args) {
-
int arr[]={
1,
8,
10,
89,
1000,
1234};
-
int index = fibSearch(arr,
89);
-
System.out.println(
"下标为"+index);
-
}
-
//因为后面我们mid=low+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 a 数组
-
* @param key 我要查找的值
-
* @return 返回对应的下标
-
*/
-
//非递归方式
-
public static int fibSearch(int[] a,int key){
-
int low=
0;
-
int high=a.length-
1;
-
int k=
0;
//斐波那契分割数值的下标
-
int mid=
0;
//存放mid值
-
int[] f=fib();
//获得fib数列
-
//获得斐波那契分割数值的下标
-
while (high>f[k]-
1){
-
k++;
-
}
-
//因为f[k] 的值可能大于 a的长度，因此我们需要使用Arrays类,构造一个新的数组,并指向a
-
int[] temp= Arrays.copyOf(a,f[k]);
-
//实际上我们需要a数组的最后的数填充temp
-
for (
int i=high+
1;i<temp.length;i++){
-
temp[i]=a[high];
-
}
-
//使用while循环，找到我们的数
-
while (low<=high){
//就可以退出
-
mid=low+f[k-
1]-
1;
-
if (key<temp[mid]){
//像数组的左边查找
-
high=mid-
1;
-
k--;
-
}
else
if (key>temp[mid]){
-
low=mid+
1;
-
k-=
2;
-
}
else{
-
if (mid<=high){
-
return mid;
-
}
else{
-
return high;
-
}
-
}
-
}
-
return -
1;
-
}
-
}
转载：https://blog.csdn.net/weixin_44076260/article/details/106170904