6.2.2 折半查找

折半查找,又称二分查找,它适用于有序的顺序表。基本思路是:首先将给定值key与表中中间位置元素的关键字比较,若相等,则查找成功,返回该元素的存储位置;若不等,则所需查找的元素只能在中间元素以外的前半部分或后半部分中(例如,在查找表升序排列时,若给定值key大于中间元素的关键字,则所查找的元素只可能在后半部分)。然后在缩小的范围内继续进行同样的查找,如此重复直到找到为止,或者确定表中没有搜需要查找的元素,则查找不成功,返回查找失败的信息。

int binary_search(SeqList L,ElemType key){
//在有序表L中查找关键字为key的元素,若存在则返回其位置,不存在则返回-1
	int low=0,high=L.tablelen-1,mid;
	while(low<=heigh){
		mid=(low+high)/2;//取中间位置
		if(L.elem[mid]==key)
			return mid;//查找成功并返回所在位置
		else if(L.elem[mid]>key)
			high=mid-1;//从前半部分继续查找
		else
			low=mid+1;//从后半部分继续查找
	}
	return -1;
}

折半查找的过程可用判定树来描述。树中每个原型结点表示一个记录,结点中的值为该记录的关键字值;树中最下面的叶结点都是方形的,它表示查找不成功的情况。查找成功是的查找长度为从根结点到目的结点的路径上的结点数,而查找不成功的查找长度为根结点到对应失败结点的父结点的路径上的结点数;每个结点值均大于其左子结点值,且均小于其右子结点值。若有序序列有n个元素,则对应的判定树有n个圆形非叶结点和n+1个方形的叶结点。

用折半查找法查找到给定值得比较次数不会超过树的高度。

在等概率查找时,查找成功的平均查找长度为

ASL=1/n*(l1+l2+……+h*2^(h-1))=[(n+1)/n]*log2(n+1)约等于log2(n+1)-1

式中,h是树的高度,并且元素个数为n时,树高h=log2(n+1) 。所以,折半查找的时间复杂度为O(log2n),平均情况下比顺序查找的效率高。

因为折半查找需要方便地定位查找区域,所以适合折半查找的存储结构必须具有随机存取的特性,因此该查找法仅适合于线性表的顺序存储结构,不适合链式存储结构,且要求元素按关键字有序排序。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏老马说编程

(41) 剖析HashSet / 计算机程序的思维逻辑

查看历史文章,请点击上方链接关注公众号。 上节介绍了HashMap,提到了Set接口,Map接口的两个方法keySet和entrySet返回的都是Set,本节,...

19590
来自专栏恰童鞋骚年

数据结构基础温故-4.树与二叉树(下)

上面两篇我们了解了树的基本概念以及二叉树的遍历算法,还对二叉查找树进行了模拟实现。数学表达式求值是程序设计语言编译中的一个基本问题,表达式求值是栈应用的一个典型...

11220
来自专栏用户3030674的专栏

Java 工具类—日期获得,随机数,系统命令,数据类型转换

15510
来自专栏IMWeb前端团队

ES6 Set

本文作者:IMWeb kurtshen 原文出处:IMWeb社区 未经同意,禁止转载 ES6 Set ES6 新增了几种集合类型,本文主要介绍Set以...

18770
来自专栏TechBox

数据结构与算法之线性表前言线性表

19950
来自专栏海天一树

二叉树的分层遍历

给定一棵二叉树,要求从上到下从左到右分层输出该二叉树的节点值。 ? bitree.png 一、递归法 二叉树本身就带有递归属性,通常我们可以用递归方法解决。假设...

29370
来自专栏JAVA高级架构

Java数据结构与算法解析——2-3树

二叉查找树对于大多数情况下的查找和插入在效率上来说是没有问题的,但是他在最差的情况下效率比较低。平衡查找树的数据结构能够保证在最差的情况下也能达到lgN的效率,...

41770
来自专栏xingoo, 一个梦想做发明家的程序员

二叉堆

容易证明: 一棵高为h的完全二叉树有2^h 到 2^(h+1)-1个结点。 这就意味着,完全二叉树的高是[logN] 特点: 任意位置i: 左儿子在位置2i上,...

21380
来自专栏自学笔记

Data Structurestackheapheap的实现索引堆tree并查集图 Graph

堆的基本性质: ①堆中的某一个节点总是不小于或不大于其父节点的值。 ②堆总是一棵完全二叉树 比较经典的堆有二叉堆,费波纳茨堆等等。如果一棵二叉树最下层上的...

10830
来自专栏赵俊的Java专栏

LeetCode 804 Unique Morse Code Words

首先为每个单词的每个字符进行转码, 将转码后的数据放到 Set 集合中, 最后返回 Set 的长度。

11340

扫码关注云+社区

领取腾讯云代金券