线性查找
线性查找又称顺序查找,是一种最简单的查找方法,它的基本思想是从第一个记录开始,逐个比较记录的关键字,直到和给定的K
值相等,则查找成功;若比较结果与文件中n
个记录的关键字都不等,则查找失败。
中文名 | 外文名 | 定义 | 应用学科 | 缩写 | 元 素 |
---|---|---|---|---|---|
线性查找 | linear search | 又称为顺序查找 | 计算机技术方法术语 | LS | 顺序查找 |
概念
线性查找又称顺序查找,是一种最简单的查找方法,它的基本思想是从第一个记录开始,逐个比较记录的关键字,直到和给定的K值相等,则查找成功;若比较结果与文件中n个记录的关键字都不等,则查找失败。
查找是对具有相同属性的数据元素(记录)的集合(数据对象)进行的,称之为表或文件,也称字典。对表的查找,若仅对表进行查找操作,而不能改变表中的数据元素,为静态查找;对表除了进行查找操作外,还可能对表进行插入或删除操作,则为动态查找。
工作原理
例如r[i].key
表示数据元素i中的关键字项。在流程图中的循环回路上要进行两次比较,即对数据元素的关键字项比较和对循环次数的判断。为了提高运算速度,可以作如下的改进:
在原表长
n
的基础上增加一个元素n+1
,将K
值送入此元素的关键字项中,这样在循环回路上只要进行一次比较,我们把第n+1
个记录称为“监视哨”。这样当n
很大时几乎可以节省一半时间。在顺序查找中,在找到第
i
个记录时,给定值K和记录中的关键字进行了i
次比较。由于平均查找长度与表长度
n
成线性关系,因此当n
较大时,顺序查找的效率较低。但顺序查找算法比较简单,且对顺序表的存储结构没有限制,既可以用向量作存储结构也可以用链表作存储结构。
Java源代码:
二分查找
二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好,占用系统内存较少;其缺点是要求待查表为有序表,且插入删除困难。因此,折半查找方法适用于不经常变动而查找频繁的有序列表。首先,假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功;否则利用中间位置记录将表分成前、后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表。重复以上过程,直到找到满足条件的记录,使查找成功,或直到子表不存在为止,此时查找不成功。
中文名 | 外文名 | 别称 | 表达式 | 提出者 | 提出时间 | 应用学科 | 适用领域范围 | 优 点 | 缺 点 |
---|---|---|---|---|---|---|---|---|---|
二分查找 | Binary-Search | 折半查找 | 无 | John Mauchly | 1946 | 计算机 | 编程语言 | 查找速度快 | 待查表为有序表 |
算法要求
- 必须采用顺序存储结构。
- 必须按关键字大小有序排列。
算法复杂度
二分查找的基本思想是将n
个元素分成大致相等的两部分,取a[n/2]
与x
做比较,如果x=a[n/2]
,则找到x
,算法中止;如果x<a[n/2]
,则只要在数组a
的左半部分继续搜索x
,如果x>a[n/2]
,则只要在数组a
的右半部搜索x
.
时间复杂度无非就是while循环的次数!
总共有n
个元素,
渐渐跟下去就是n,n/2,n/4,....n/2^k
(接下来操作元素的剩余个数),其中k
就是循环的次数
由于你n/2^k
取整后>=1
即令n/2^k=1
可得k=log2n
,(是以2
为底,n
的对数)
所以时间复杂度可以表示O(h)=O(log2n)
下面提供一段二分查找实现的伪代码:
|
|
折半查找法也称为二分查找法,它充分利用了元素间的次序关系,采用分治策略,可在最坏的情况下用O(log n)
完成搜索任务。它的基本思想是,将n
个元素分成个数大致相同的两半,取a[n/2]
与欲查找的x
作比较,如果x=a[n/2]
则找到x
,算法终止。如 果x<a[n/2]
,则我们只要在数组a
的左半部继续搜索x
(这里假设数组元素呈升序排列)。如果x>a[n/2]
,则我们只要在数组a
的右 半部继续搜索x
。
Java源代码: