书接上回:算法系列一:顺序查找、二分查找、分块查找
上一篇的二分查找中,每次查找都是从待查序列的中间开始,那么就很容易想到一个问题或者场景:假设我有一个数组0~999,我要查找的数为900,如果按照二分查找,那我每次取中间值要查找好一会,我们从上帝视角看明显可以从靠后的位置去查。于是针对这种情况,出现了插值查找。
区别对比:
① 插值查找类似于二分法,但插值查找每次从自适应 mid 处开始查找;
② 二分查找种mid为(left+right) / 2, 插值查找则是通过公式计算得来;
③ 插值查找公式:int mid = low + (high - low) * (key - arr[low]) / (arr[high] - arr[low]) ;low表示左边索引left,high表示右边索引right. key 就是需要查找的值。
插值查找特点:
① 查找序列有序;
② 数据量大、关键字分布均匀的有序序列,插值查找快;
③ 对于分布不均匀的有序序列来说,不一定比二分查找好。
① 迭代法查找:
private static int insertSearch1(int arr[],int target){
/*初始化左右搜索边界*/
int left=0,right=arr.length-1;
int mid;
while(left<=right){
mid=left+(target-arr[left])/(arr[right]-arr[left])*(right-left);
/*arr[mid]大于target,即要寻找的元素在左半边,所以需要设定右边界为mid-1,搜索左半边*/
if(target<arr[mid]){
right=mid-1;
/*arr[mid]小于target,即要寻找的元素在右半边,所以需要设定左边界为mid+1,搜索右半边*/
}else if(target>arr[mid]){
left=mid+1;
/*搜索到对应元素*/
}else if(target==arr[mid]){
return mid;
}
}
/*搜索不到返回-1*/
return -1;
}
② 递归法实现:
private static int insertSearch2(int array[],int left,int right,int target){
if(left<=right){
int mid=left+(target-array[left])/(array[right]-array[left])*(right-left);
/*搜索到对应元素*/
if(array[mid]==target){
return mid;
}else if(array[mid]<target){
/*array[mid]小于target,即要寻找的元素在右半边,所以需要设定左边界为mid+1,搜索右半边*/
return insertSearch2(array,mid+1,right,target);
}else{
/*array[mid]大于target,即要寻找的元素在左半边,所以需要设定右边界为mid-1,搜索左半边*/
return insertSearch2(array,left,mid-1,target);
}
}else{
return -1;
}
}
斐波那契查找又名黄金分割查找算法。
算法原理:
斐波那契查找原理与二分查找算法和插值查找算法非常相似,仅仅改变了中间节点(mid)的位置,mid不再是中间或插值得到,而是位于黄金分割点附近,即mid=low+F(k-1)-1(F代表斐波那契数列)。
???怎么理解这里的mid
while(n>fib(k)-1){
k++;
}
public class FibonacciSearch {
public static int FLENGTH = 20;
public static void main(String[] args) {
int [] arr = {1,8,10,89,100,134};
int target = 89;
System.out.println("目标元素在数组中位置是:" + fibSearch(arr, target));
}
public static int[] fib() {
int[] f = new int[FLENGTH];
f[0] = 1;
f[1] = 1;
for (int i = 2; i < FLENGTH; i++) {
f[i] = f[i-1] + f[i-2];
}
return f;
}
public static int fibSearch(int[] arr, int target) {
int low = 0;
int high = arr.length - 1;
int k = 0;
int mid = 0;
int f[] = fib();
/*获取最相邻的斐波那契数组中元素的值,该值略大于数组的长度*/
while(high > f[k] - 1) {
k++;
}
/*因为 f[k]值可能大于arr的长度。如果大于时,需要构造一个新的数组temp[],将arr数组中的元素拷贝过去,不足的部分会使用0填充*/
int[] temp=Arrays.copyOf(arr, f[k]);
/*然后将temp后面填充的0,替换为最后一位数字
*如将temp数组由{1,8,10,89,100,134,0,0}变换为{1,8,10,89,100,134,134,134}*/
for(int i = high + 1; i < temp.length; i++) {
temp[i] = arr[high];
}
while (low <= high) {
mid = low + f[k - 1] - 1;
if(target < temp[mid]) {
high = mid - 1;
/*因为f[k]=f[k-1]+f[k-2],所以k--就相当于取temp数组的左边部分*/
k--;
} else if ( target > temp[mid]) {
low = mid + 1;
/*同理,f[k]=f[k-1]+f[k-2],k -= 2就相当于取temp数组的右边部分*/
k -= 2;
} else {
/*原arr数组中的值*/
if(mid <= high){
return mid;
/*在temp中,扩展出来的高位的值*/
}else{
return high;
}
}
}
return -1;
}
}
这里的算法实现可以理解可以看这位博主
活动地址:CSDN21天学习挑战赛