在要求输入邮箱的文本域,请填写真实的邮件地址。非真实邮件地址,将收不到回复信息。

七种查找算法

数据结构与算法 清风 359℃ 0评论

查找是在大量的信息中寻找一个特定的信息元素,在计算机应用中,查找是常用的基本运算,例如编译程序中符号表的查找。由于查找运算的使用频率很高,几乎在任何一个计算机系统软件和应用软件中都会涉及到,所以当问题所涉及的数据量相当大时,查找方法的效率就显得格外重要。

查找定义:根据给定的某个值,在查找表中确定一个其关键字等于给定值的数据元素(或记录)。

  查找算法分类:
  1)静态查找和动态查找;
    注:静态或者动态都是针对查找表而言的。动态表指查找表中有删除和插入操作的表。
  2)无序查找和有序查找。
    无序查找:被查找数列有序无序均可;
    有序查找:被查找数列必须为有序数列。
  平均查找长度(Average Search Length,ASL):需和指定key进行比较的关键字的个数的期望值,称为查找算法在查找成功时的平均查找长度。
  对于含有n个数据元素的查找表,查找成功的平均查找长度为:ASL = Pi*Ci的和。
Pi:查找表中第i个数据元素的概率。
Ci:找到第i个数据元素时已经比较过的次数。
  • 顺序查找(Sequential Search)

在表的组织方式中,线性表是最简单的一种。顺序查找是一种最简单的查找方法。

1、顺序查找的基本思想
基本思想是:从表的一端开始,顺序扫描线性表,依次将扫描到的结点关键宇和给定值K相比较。若当前扫描到的结点关键字与K相等,则查找成功;若扫描结束后,仍未找到关键字等于K的结点,则查找失败。

2、顺序查找的存储结构要求
顺序查找方法既适用于线性表的顺序存储结构,也适用于线性表的链式存储结构(使用单链表作存储结构时,扫描必须从第一个结点开始)。

3、复杂度分析:
查找成功时的平均查找长度为:(假设每个数据元素的概率相等) ASL = 1/n(1+2+3+…+n) = (n+1)/2 ;当查找不成功时,需要n+1次比较,时间复杂度为O(n);所以,顺序查找的时间复杂度为O(n)。

4、顺序查找的优点
算法简单,且对表的结构无任何要求,无论是用向量还是用链表来存放结点,也无论结点之间是否按关键字有序,它都同样适用。

5、顺序查找的缺点
查找效率低,因此,当n较大时不宜采用顺序查找

C# 语言实现:


public int SequentialSearch(int[] data, int key) 
{
	int len = data.Length;
	int index=-1;
	for (int i = 0; i < len; i++) 
	{
		if (data[i] == key) 
		{
			index = i;
			break;
		}
	}
	return index;
}

转载请注明:清风博客 » 七种查找算法

喜欢 (0)or分享 (0)
支付宝扫码打赏 微信打赏
发表我的评论
取消评论

CAPTCHA Image
Reload Image
表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址