java数据结构之插值查找和斐波那契查找
程序员文章站
2022-07-12 09:51:41
...
插值查找:
二分查找在确定中间值的位置的时候,使用的公式为:
mid = (right + left) / 2
此公式可以转换为:mid = left + (right - left) / 2
上面的公式中 1/2 我们可以进行优化:
设要查找的值为 targetVal
(targetVal - a[left]) / (a[right] - a[left]) * (right - left)
此公shi能够比较快速的定位到 targetVal倾向于偏到哪一个方向
因此有 mid = left + (right - left) * (targetVal - a[left]) / (a[right] - a[left])
优于 mid = left + (right - left) / 2,同样插值查找也需要数组是有序的,在a中的值分布不均匀,跳跃性很大的
情况下,插值查找不一定比二分查找好
代码:
public class InsertValueSearch {
public static void main(String[] args) {
int len = 100;
int[] a = new int[len];
for ( int i = 0; i < len; i++) {
a[i] = i;
}
int findVal = 45;
int pos = insertSearch(a, 0, a.length-1, findVal);
System.out.printf("要查找的值为:%d, pos:%d\n", findVal, pos);
}
//找到返回对应的下标,找不到返回-1
public static int insertSearch(int a[], int left, int right, int findVal) {
System.out.println("Hello~~");
//插值查找 findVal < a[left] || a[right] < findVal 必须有
if (left > right || findVal < a[left] || a[right] < findVal) {
return -1;
}
int mid = left + (right - left) * (findVal - a[left]) / (a[right] - a[left]);
int midVal = a[mid];
if (findVal > midVal) {
return insertSearch(a, mid+1, right, findVal);
} else if (findVal < midVal) {
return insertSearch(a, left, mid-1, findVal);
} else {
return mid;
}
}
}
斐波那契查找
0.618让人看了很舒服 在二分查找确定 1/2的时候,我们可以确定0.618 斐波那契数前一个数比上后一个数的比例接近于0.618
代码:
public class FibonacciSearch {
public static void main(String[] args) {
int len = 100;
int[] a = new int[len];
for ( int i = 0; i < len; i++) {
a[i] = i;
}
int[] a1 = {1, 8, 10,89,1000,1234};
int findVal = 45;
int i = fibonacciSearch(a1, findVal);
}
public static int fibonacciSearch(int a[], int findVal) {
int low = 0;
int high = a.length - 1;
int k = 0;
int mid = 0; //
int f[] = fib(20);
//获取到斐波那契数值的下标
while (high > f[k] - 1) {
k++;
}
//因为f[k] 值可能大于数组的长度,因此使用Arrays类构造一个新的数组,并指向a[]
//不足的部分使用0填充
int[] tmp = Arrays.copyOf(a, f[k]);
//需要使用a数组最后的数填充tmp
for (int i = high+1; i < tmp.length; i++) {
tmp[i] = a[high];
}
//循环查找,直到找到目标数
while (low <= high) {
mid = low + f[k-1] -1;
if (findVal < tmp[mid]) { //向数组前面查找
high = mid-1;
k--; //全部元素 = 前面的元素 + 后面的元素。 f[k] = f[k-1] + f[k-2]
//前面有f[k-1]个元素,所以可以继续拆分 f[k-1] = f[k-2] + f[k-3],即在f[k-1]的前面继续查找
} else if (findVal > tmp[mid]) { //想数组后面查找
low = mid+1;
k -= 2; //全部元素 = 前面元素 + 后面元素
//f[k] = f[k-1]+ f[k-2], 因为f
} else {
//需要确定返回的是哪一个坐标
if (mid <= high) {
return mid;
} else {
return high;
}
}
}
return -1;
}
//非递归方法获取斐波那契数列
public static int[] fib(int maxSize) {
int[] f = new int[maxSize];
if (maxSize < 2) {
f = new int[2];
}
f[0]= 1;
f[1] = 1;
for (int i = 2; i < f.length; i++) {
f[i] = f[i-1]+f[i-2];
}
return f;
}
}