当前位置:网站首页>Interpolation lookup (two methods)
Interpolation lookup (two methods)
2022-07-07 08:37:00 【S dream chasing boy】
One 、 What is interpolation lookup
(1) Interpolation search algorithm is similar to binary search , The difference is that the interpolation lookup starts from The adaptive mid It's about Start looking for .
(2) Binary search mid The value is left and right The sum of the subscripts of the indicated sequence 1/2 namely mid = (left+right)/ 2.
(3) And interpolation search mid The value is calculated by formula , It is obvious from the formula mid The value of is not the middle position of the left and right indexes like dichotomy .
(4) Interpolation search formula ;3、int mid = low + (high - low) * (key - arr[low]) / (arr[high] - arr[low]) ;low Indicates the index on the left left,high Indicates the index on the right right. key Is the value you need to find .
Two 、 Features of interpolation search
(1) The search sequence must be ordered
(2) about Large amount of data And keywords Evenly distributed For the ordered sequence of , Interpolation search is faster .
(3) about Unevenly distributed For the ordered sequence of , This algorithm is not necessarily better than binary search .
3、 ... and 、 Code implementation
(1) Method 1 : recursive
public class InterpolationSearch {
public static void main(String[] args) {
int [] arr= {1,3,9,12,14,17,24,28,29};
int low = 0;
int high = arr.length-1;
int index = interpolationSearch(arr,low,high,17);
System.out.print(" Element found 17 The location of the for :"+index);
}
public static int interpolationSearch(int[] arr, int low, int high, int key) {
if (low > high) {
return -1;
}
int mid = low + (int) (1.0 * (key - arr[low]) / (arr[high] - arr[low]) * (high - low));
if (mid < low || mid > high) {
return -1;
}
if (arr[mid] == key) {
return mid;
} else if (key < arr[mid] ) {
return interpolationSearch(arr,low,mid - 1,key);
} else {
return interpolationSearch(arr,mid + 1, high,key);
}
}
}
Running results :
(2) Method 2 : iteration
public class InterpolationSearch {
public static void main(String[] args) {
int[] arr = { 1, 3, 9, 12, 14, 17, 24, 28, 29 };
int index = insertvaluesearch(arr, 17);
System.out.print(" Element found 17 The location of the for :" + index);
}
public static int insertvaluesearch(int arr[], int key) {
int low = 0;
int high = arr.length - 1;
while (low <= high) {
int mid = low + (high - low) * (key - arr[low]) / (arr[high] - arr[low]);
if (arr[mid] == key) {
return mid;
}
if (arr[mid] < key) {
low = mid + 1;
}
if (arr[mid] > key) {
high = mid - 1;
}
}
return -1;
}
}
Running results :
边栏推荐
- Composer change domestic image
- Fluentd is easy to use. Combined with the rainbow plug-in market, log collection is faster
- How to integrate app linking services in harmonyos applications
- [Chongqing Guangdong education] audio visual language reference materials of Xinyang Normal University
- MES系统,是企业生产的必要选择
- Obsidan之数学公式的输入
- uniapp 微信小程序监测网络
- Leetcode 1984. Minimum difference in student scores
- [kuangbin]专题十五 数位DP
- 为什么要选择云原生数据库
猜你喜欢
MySQL introduction - crud Foundation (establishment of the prototype of the idea of adding, deleting, changing and searching)
Openvscode cloud ide joins rainbow integrated development system
2-3查找树
Obsidan之数学公式的输入
一种适用于应用频繁测试下快速查看Pod的日志的方法(grep awk xargs kuberctl)
GFS distributed file system
let const
[untitled]
Improve the delivery efficiency of enterprise products (1) -- one click installation and upgrade of enterprise applications
快速集成认证服务-HarmonyOS平台
随机推荐
关于基于kangle和EP面板使用CDN
Fluentd is easy to use. Combined with the rainbow plug-in market, log collection is faster
IELTS review progress and method use [daily revision]
测试踩坑 - 当已有接口(或数据库表中)新增字段时,都需要注意哪些测试点?
SSM 整合
AVL balanced binary search tree
Rainbow combines neuvector to practice container safety management
You should use Google related products with caution
IP-guard助力能源企业完善终端防泄密措施,保护机密资料安全
opencv 将16位图像数据转为8位、8转16
Tronapi-波场接口-源码无加密-可二开--附接口文档-基于ThinkPHP5封装-作者详细指导-2022年7月6日-新手快速上手-可无缝升级tp6版本
Several ways of lambda used in functions in kotlin (higher-order functions)
A single game with goods increased by 100000, and the rural anchor sold men's clothes on top of the list?
2 - 3 arbre de recherche
Are you holding back on the publicity of the salary system for it posts such as testing, development, operation and maintenance?
let const
[untitled]
字符串操作
PVTV2--Pyramid Vision TransformerV2学习笔记
Input of mathematical formula of obsidan