尚硅谷Java数据结构--插值查找(二分查找改进)
在二分查找中:
m
i
d
=
(
l
e
f
t
+
r
i
g
h
t
)
/
2
=
l
e
f
t
+
1
2
(
r
i
g
h
t
−
l
e
f
t
)
mid=(left+right)/2=left+\frac{1}{2}(right-left)
mid=(left+right)/2=left+21(right−left)
而在插值查找中:
m
i
d
=
l
e
f
t
+
t
a
r
g
e
t
−
a
r
r
[
l
e
f
t
]
a
r
r
[
r
i
g
h
t
]
−
a
r
r
[
l
e
f
t
]
(
r
i
g
h
t
−
l
e
f
t
)
mid=left+\frac{target-arr[left]}{arr[right]-arr[left]}(right-left)
mid=left+arr[right]−arr[left]target−arr[left](right−left)
插值查找算法相对于二分查找可以更加精确的定位target所在的位置
以下是二分查找和插值查找的代码
package DataStructure;
import java.util.ArrayList;
import java.util.Arrays;
/**
* Created with IntelliJ IDEA.
* Description:
* User: 86178
* Date: 2024-02-29
* Time: 12:44
*/
public class FindVal {
static int binaryCnt=0;
static int inserCnt=0;
public static void main(String[] args) {
int[] arr=new int[100];
for(int i=0;i<arr.length;i++){
arr[i]=i+1;
}
/*for (int i : arr) {
System.out.print(i+" ");
}*/
//todo 返回下标
System.out.println("查找数字1");
System.out.println("二分查找下标返回"+BinarySearch(arr, 0, arr.length - 1, 1 ));
System.out.println("二分查找调用次数:"+binaryCnt);
System.out.println("插值查找下标返回"+InsertSearch(arr, 0, arr.length - 1, 1 ));
System.out.println("插值查找调用次数:"+inserCnt);
}
public static int BinarySearch(int[] arr,int left,int right,int target){
binaryCnt++;
if(left>right) return -1;
int mid=(left+right)/2;
if(target==arr[mid]) return mid;
else if(target>arr[mid]) return BinarySearch(arr,mid+1,right,target);
else return BinarySearch(arr,left,mid-1,target);
}
public static int InsertSearch(int[] arr,int left,int right,int target){
inserCnt++;
/*
todo 其中 target<arr[0] || target>arr[arr.length-1] 的判断是必须的
因为 mid=left+(target-arr[left])/(arr[right]-arr[left])*(right-left);
当target非常大的时候 会出现下标越界
*/
if(left>right || target<arr[0] || target>arr[arr.length-1]) return -1;
int mid=left+(target-arr[left])/(arr[right]-arr[left])*(right-left);
if(target==arr[mid]) return mid;
else if(target>arr[mid]) return InsertSearch(arr,mid+1,right,target);
else return InsertSearch(arr,left,mid-1,target);
}
}
其中插值查找需要注意mid下标越界问题
原文地址:https://blog.csdn.net/m0_70094411/article/details/136370940
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!