前两篇
《程序员必知8大排序3大查找(一)》
《程序员必知8大排序3大查找(二)》
三种查找算法:顺序查找,二分法查找(折半查找),分块查找,散列表(以后谈)
一、顺序查找的基本思想:
从表的一端开始,顺序扫描表,依次将扫描到的结点关键字和给定值(假定为a)相比较,若当前结点关键字与a相等,则查找成功;若扫描结束后,仍未找到关键字等于a的结点,则查找失败。
说白了就是,从头到尾,一个一个地比,找着相同的就成功,找不到就失败。很明显的缺点就是查找效率低。
适用于线性表的顺序存储结构和链式存储结构。
计算平均查找长度。
例如上表,查找1,需要1次,查找2需要2次,依次往下推,可知查找16需要16次,
可以看出,我们只要将这些查找次数求和(我们初中学的,上底加下底乘以高除以2),然后除以结点数,即为平均查找长度。
设n=节点数
平均查找长度=(n+1)/2
二、二分法查找(折半查找)的基本思想:
前提:
(1)确定该区间的中点位置:mid=(low+high)/2
min代表区间中间的结点的位置,low代表区间最左结点位置,high代表区间最右结点位置
(2)将待查a值与结点mid的关键字(下面用R[mid].key)比较,若相等,则查找成功,否则确定新的查找区间:
如果R[mid].key>a,则由表的有序性可知,R[mid].key右侧的值都大于a,所以等于a的关键字如果存在,必然在R[mid].key左边的表中。这时high=mid-1
如果R[mid].key<a,则等于a的关键字如果存在,必然在R[mid].key右边的表中。这时low=mid
如果R[mid].key=a,则查找成功。
(3)下一次查找针对新的查找区间,重复步骤(1)和(2)
(4)在查找过程中,low逐步增加,high逐步减少,如果high<low,则查找失败。
平均查找长度=Log2(n+1)-1
注:虽然二分法查找的效率高,但是要将表按关键字排序。而排序本身是一种很费时的运算,所以二分法比较适用于顺序存储结构。为保持表的有序性,在顺序结构中插入和删除都必须移动大量的结点。因此,二分查找特别适用于那种一经建立就很少改动而又经常需要查找的线性表。
三、分块查找的基本思想:
二分查找表使分块有序的线性表和索引表(抽取各块中的最大关键字及其起始位置构成索引表
)组成,由于表是分块有序的,所以索引表是一个递增有序表,因此采用顺序或二分查找索引表,以确定待查结点在哪一块,由于块内无序,只能用顺序查找。
设表共n个结点,分b块,s=n/b
(分块查找索引表)平均查找长度=Log2(n/s+1)+s/2
(顺序查找索引表)平均查找长度=(S2+2S+n)/(2S)
注:分块查找的优点是在表中插入或删除一个记录时,只要找到该记录所属块,就在该块中进行插入或删除运算(因块内无序,所以不需要大量移动记录)。它主要代价是增加一个辅助数组的存储控件和将初始表分块排序的运算。
它的性能介于顺序查找和二分查找之间。
四、最近比较忙,后续找个时间还会谈谈散列表(哈希表)技术,希望大家关注!
散列表查找技术不同于顺序查找、二分查找、分块查找。它不以关键字的比较为基本操作,采用直接寻址技术。在理想情况下,无须任何比较就可以找到待查关键字,查找的期望时间为O(1)。
前两篇
《程序员必知8大排序3大查找(一)》
《程序员必知8大排序3大查找(二)》
感谢大家的支持,无论是顶的,还是踩的,都谢谢你们,希望大家互相关注,共同进步。
分享到:
相关推荐
此文档中不紧包括8大排序3大查找算法的基本思想,而且还附上有每种算法实现的源码,还有清楚明了的图文解析,更加易懂。对于一个程序员来讲,要编写出优秀的代码同样要扎实的基础,如果排序和查找算法学的不好,怎么...
每天都在叫嚣自己会什么技术,什么框架,可否意识到你每天都在被这些新名词、新技术所迷惑,.NET、XML等等技术固然诱人,可是如果自己的基础不...废话不多说,本文要介绍的这些排序算法就是基础中的基础,程序员必知!
Java常用排序算法&程序员必须掌握的8大排序算法+二分法查找 Java常用排序算法&程序员必须掌握的8大排序算法+二分法查找
Java常用排序算法&程序员必须掌握的8大排序算法+二分法查找(同步到博客).doc
本书作者介绍了一些有用但很少被讨论的算法,它们可用于语音查找、日期和时间例程(直到公元1年)、B树和索引文件、数据压缩、任意精度的算术、校验和与数据验证,并且还最全面地介绍了查找例程、排序算法和数据结构...
本书(程序员常用算法)重点关注的是实用,立即可用的代码,并且广泛...日期和时间例程(直到公元1年)、B树和索引文件、数据压缩、任意精度的算术,校验和与数据验证,并且全面地介绍了查找例程、排序算法和数据结构。..
1.2.10 DBA与程序员 第2章 数据表的创建和管理 2.1 数据类型 2.1.1 整数类型 2.1.2 数值类型 2.1.3 字符相关类型 2.1.4 日期时间类型 2.1.5 二进制类型 2.2 通过SQL语句管理数据表 2.2.1 创建数据...
专业的程序设计人员常被称为程序员。 2.程序设计=数据结构+算法 Programming = Data Structures + Algorithm 3.程序设计:为计算机处理问题编制一组指令集。 算法:处理问题的策略。 数据结构:问题的数学模型。...
第3章 散列 3.1 散列的概念 3.2 散列函数 3.3 冲突解决方法 3.3.1 线性再散列法 3.3.2 非线性再散列法 3.3.3 外部拉链法 3.4 性能问题 3.5 资源和参考资料 第4章 查找 4.1 查找的特征 ...
1.2.10 DBA与程序员 第2章 数据表的创建和管理 2.1 数据类型 2.1.1 整数类型 2.1.2 数值类型 2.1.3 字符相关类型 2.1.4 日期时间类型 2.1.5 二进制类型 2.2 通过SQL语句管理数据表 2.2.1 创建数据...
o 2.2 寻找和为定值的两个数 o 2.3 寻找和为定值的多个数 o 2.4 最大连续子数组和 o 2.5 跳台阶 o 2.6 奇偶排序 o 2.7 荷兰国旗 o 2.8 矩阵相乘 o 2.9 完美洗牌 o 2.15 本章习题 第三章 树 o 3.0 本章导读 o 3.1 ...
【作 者】(美)DonaldE.Knuth著 【内容提要】 关于算法分析的这多卷论著已经长期被公认为经典计算机科学的定义性描述。迄今已出版的完整的三卷已经组成了程序设计理论和实践...第3卷为排序和查找,分“排序”和“...
详细介绍了直接插入排序、希尔排序、简单选择排序、堆排序、冒泡排序、快速排序、归并排序、基数排序等
1.2.10 DBA与程序员 第2章 数据表的创建和管理 2.1 数据类型 2.1.1 整数类型 2.1.2 数值类型 2.1.3 字符相关类型 2.1.4 日期时间类型 2.1.5 二进制类型 2.2 通过SQL语句管理数据表 2.2.1 创建数据...
程序员面试题精选 100 题(01)-把二元查找树转变成排序的 双向链表 题目:输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点, 只调整指针的指向。 程序员面试题精选 100 题...
无论您是Java编程的初学者还是有经验的程序员,该资源都将为您提供有价值的指导和支持,帮助您掌握Java中实现有序矩阵查找的方法。我们相信,该资源将成为想提高算法设计技能的Java程序员的宝贵参考资料。
日期和时间例程(直到公元1年)、B树和索引文件、数据压缩、任意精度的算术,校验和与数据验证,并且全面地介绍了查找例程、排序算法和数据结构。.. 本书只要求读者具有C语言的初级知识以及基本代数的相关知识。源代码...
1.2.10 DBA与程序员 第2章 数据表的创建和管理 2.1 数据类型 2.1.1 整数类型 2.1.2 数值类型 2.1.3 字符相关类型 2.1.4 日期时间类型 2.1.5 二进制类型 2.2 通过SQL语句管理数据表 2.2.1 创建数据...
1.2.10 DBA与程序员 第2章 数据表的创建和管理 2.1 数据类型 2.1.1 整数类型 2.1.2 数值类型 2.1.3 字符相关类型 2.1.4 日期时间类型 2.1.5 二进制类型 2.2 通过SQL语句管理数据表 2.2.1 创建数据...