C#算法设计查找篇之03-插值查找
2024-09-30 01:18:39
插值查找(Interpolation Search)
该文章的最新版本已迁移至个人博客【比特飞】,单击链接 https://www.byteflying.com/archives/701 访问。
插值查找是二分查找的更高效版本,它不会每次按2平分原问题规模,而是应用一个技巧来尽快的接近目标关键字。
示例:
public class Program {
public static void Main(string[] args) {
int[] array = { 8, 11, 21, 28, 32, 43, 48, 56, 69, 72, 80, 94 };
Console.WriteLine(InterpolationSearch(array, 80, 0, array.Length - 1));
Console.ReadKey();
}
private static int InterpolationSearch(int[] array, int key, int low, int high) {
if (low > high) return -1;
var mid = (int)(low + ((double)key - array[low]) /
(array[high] - array[low]) * (high - low));
if (array[mid] == key)
return mid;
else if (array[mid] > key)
return InterpolationSearch(array, key, low, mid - 1);
else
return InterpolationSearch(array, key, mid + 1, high);
}
}
请注意以上递归实现为尾递归,详情参考我的另一篇博文:
C#开发笔记之06-为什么要尽可能的使用尾递归,编译器会为它做优化吗?
以上是插值查找算法的一种实现,以下是这个案例的输出结果:
该文章的最新版本已迁移至个人博客【比特飞】,单击链接 https://www.byteflying.com/archives/701 访问。
10
分析:
在最坏的情况下插值查找的时间复杂度为: 。
最新文章
- c#文件操作
- 从问题看本质:socket到底是什么?
- [No00007D]2016-面经[上]
- AngularJS Select(选择框)
- Custom Web Servic In MOSS 2007
- Mysql分布式事务
- 二模 (13)day1
- [ES6] 15. Generators -- 2
- [Hive - Tutorial] Built In Operators and Functions 内置操作符与内置函数
- Html——footer的使用
- [PWA] Keynote: Progressive Web Apps across all frameworks
- mssql分页原理及效率分析
- spoj1811:Longest Common Substrin
- FZU 2086 餐厅点餐(枚举)
- S-CMS企建v3二次SQL注入
- instance of的java用法
- chapter15中使用generator来实现异步化操作的同步化表达的例子
- iOS - 极光推送证书的创建及过期处理
- Nuxtjs初始
- HDUOJ---2955 Robberies
热门文章
- 搭建jmeter+influxdb+grafana压测实时监控平台(超详细,小白适用)
- 题解 洛谷 P4632 【[APIO2018] New Home 新家】
- Kafka 入门(一)--安装配置和 kafka-python 调用
- web自动化 -- HTMLreport(二)测试报告输出内容居左对齐
- set自动排序去重 stringstream流分割字符
- vue -电子时钟
- 用友U8API 8.9-15.0接口开发前提,选好开发方式
- PHP mysqli_thread_safe() 函数
- PHP addcslashes() 函数
- luogu P4206 [NOI2005]聪聪与可可 期望dp 记忆化搜索