文档章节

常用的查找算法(末)

魍宂庞
 魍宂庞
发布于 05/27 12:26
字数 947
阅读 38
收藏 0

「深度学习福利」大神带你进阶工程师,立即查看>>>

三:插值查找

插值查找类似二分查找,不同点在于二分查找是从mid中值开始,而插值查找可以从自己定义的mid处开始查找,同样达到二分查找的效果,并且效率比二分查找好一点。

(二分查找法公式——插值查找法公式)(findval是要查找的值)

mid = (low + high) / 2——mid = low + (high - low) * findval - arr[low] / arr[high] - arr[low]

思路:

1、整体思路和二分查找算法是类似的,重点在于mid的公式变化。

2、若找不到则返回-1;由于是有序数列,可知头必然是最小值,尾必然是最大值,所以要预防查找的值越界。

测试代码:

public class InsertValueSearch {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		//在数组中添加一百个数
		int [] arr = new int [100];
		for( int i = 0; i < 100; i++) {
			arr[i] = i+1;
		}
		
		int value = insertvaluesearch(arr,0,arr.length-1,99);
		System.out.println("插值查找的值为" + value);
	}

	public static int insertvaluesearch(int [] arr,int left,int right,int findVal) {
		//首先考虑查找不到,返回-1
		//为了优化插值查找,并且防止出现越界问题,使用 或|| 逻辑进行判断
		if(left > right || findVal < arr[0] || findVal > arr[arr.length-1]) {
			return -1;
		}
		//定义中值_使用公式low + (high - low)* findVal - arr[low] / arr[high] - arr[low]
		int midvalue = left + (right - left) * (findVal - arr[left]) / (arr[right] - arr[left]);
		int mid = arr[midvalue];
		//进行判断
		if(findVal < mid) {	//说明要查找的值在mid左边
			return insertvaluesearch(arr, left, mid - 1, findVal);
		} else if(findVal > mid) {	//说明要查找的值在mid右边
			return insertvaluesearch(arr, mid + 1, right, findVal);
		} else {	//否则则表示要查找的值与mid相等,返回即可
			return mid;
		}
	}
}

插值查找注意点:

1、数据量比较大,而且关键字分布均匀的查找表,采用插值查找效率比二分快。

2、关键字分布 ‘不均匀(指查找表之间的数据元素跳跃幅度过大。例如1,2,100,999)’,此时效果不一定不二分查找快;对于实际应用,到时候根据实际情况测试再选择即可。

四:斐波那契查找(黄金分割法)

为什么黄金分割法又叫做斐波那契查呢?

因为斐波那契相邻两个数的比例无限接近黄金分割值0.618。

斐波那契查找法是基于黄金分割点的基础,借助了斐波那契数列的特性(最初两个数是 1 和 1 ,后面的数是前面两个数之和)来对有序数组进行查找。

斐波那契查找原理:

主要的实现还是和二分查找是相似的,不同的在于mid中间值的改变。

我们要查找的值会在黄金分割点附近,只需要使我们的数组的值满足斐波那契数列的规律(代码实现,即对原本的数组进行扩容),就可以找到数组中的黄金分隔点,也就是我们要查找的值。

斐波那契数列规律(k表示元素位置):F[k] = f[k-1] + f[k-2]   ==   F[k]-1 =( (F[k]-1) + (F[k]-2) + 1)重点在于+1和-1.

思路:  

1、创建斐波那契数列

2、找到斐波那契分店树脂道位置

3、替换数组(f[k]的值可能大于原本的数组)

4、具体实现查找(和二分查找的结构类似,条件不同),找不到返回-1,调用检查

测试代码:

魍宂庞
粉丝 0
博文 61
码字总数 43218
作品 0
广州
私信 提问
加载中
请先登录后再评论。
Android传感器API之:磁场Magnetic Field源码与示例

Android的磁场传感器,Magnetic Field。。读取磁场的变化,通过该传感器可开发出指南针、罗盘等磁场应用。该传感器读取的数据是空间坐标系三个方向的磁场值,其数据单位为uT,即微特斯拉。 ...

DSALK
2011/11/30
2.8K
2
电影浏览器movbrow(linux版)

电影浏览器movbrow 是一个搜索、播放盘上视频的软件 搜索多个指定文件夹下的视频,默认是用户目录下的视频文件夹 按照文件实际格式来查找视频,不是根据后缀名,然后会查找一个跟他同名的后缀...

zzzzzzzzzzz
2010/10/26
738
4
JCF框架源码分析系列-ArrayList(二)

1、揭开ArrayList真面目 作者将在本文详细赘述日常开发中最常用集合类-ArrayList,本次JCF源码分析基于JDK1.7,主要从以下几个方向分析: UML类图关系 数据结构 接口介绍 常用、重要方法的实...

Ambitor
2015/11/30
385
0
使用elasticsearch1.5.2实现查找附近的人

pom.xml: <project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://mav......

凯文加内特
2015/10/12
4.1K
4
JDK高性能编程之容器

JDK高性能编程之容器 读书笔记内容部分来源书籍深入理解JVM、互联网等,如有错误,请指正,我会及时更正,感谢。 先放一个类图util,点击打开看明细 j360-jdk调试功能 https://github.com/x...

Hi徐敏
2015/10/17
6.7K
18

没有更多内容

加载失败,请刷新页面

加载更多

MySQL索引相关

一、索引分类 1、单列索引 1.1、主键索引(不能包含空值) 1.2、唯一索引(可以包含kong'zhi) 1.3、普通索引 2、多列索引 2.1、组合索引 3、全文索引 3.1、全文索引只针对大文本字段有效,比如:...

城里的月光
今天
21
0
二级分销的理解

人人商城分销定义 例如: 分销商:A、B、C、D、E 群体1:A是B的上级分销商,B是C的上级分销商,C是D的上级分销商,则他们分销层级是:A是一级分销商,B是二级分销商,C是三级分销商 群体2:B...

红翼网
今天
6
0
HBase/TiDB都在用的数据结构:LSM Tree,不得了解一下?

LSM Tree(Log-structured merge-tree)广泛应用在HBase,TiDB等诸多数据库和存储引擎上,我们先来看一下它的一些应用: 这么牛X的名单,你不想了解下LSM Tree吗?装X之前,我们先来了解一些...

Monica2333
今天
26
0
Linux下如何高效切换目录?

Linux 下对于目录的切换,大家肯定会想到一个命令:cd 命令。这个是 Linux 下再基本不过的命令,如果这个命令都不知道的话,赶紧剖腹自尽去吧。 cd 命令确实很方便,但如果需要频繁在下面的目...

良许Linux
今天
59
0
限流算法

1 计数算法 2 滑动窗口 (可以解决计数算法 临界线 QPS超过限流问题) 3 漏桶算法 4 令牌桶算法

yzzzzzzzz
今天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部