常用的7大查找算法之二:二分查找(折半查找)

2017-04-23 17:21 阅读 978 次 评论 0 条

1.查找算法概述

查找是在大量的信息中寻找一个特定的信息元素,在计算机应用中,查找是常用的基本运算,例如编译程序中符号表的查找。本文简单概括性的介绍了常见的七种查找算法,说是七种,其实二分查找、插值查找以及斐波那契查找都可以归为一类——插值查找。插值查找和斐波那契查找是在二分查找的基础上的优化查找算法。树表查找和哈希查找会在后续的博文中进行详细介绍。

(1)查找定义

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

(2)查找算法分类

1)静态查找和动态查找

注:静态或者动态都是针对查找表而言的。动态表指查找表中有删除和插入操作的表。

2)无序查找和有序查找

无序查找:被查找数列有序无序均可;

有序查找:被查找数列必须为有序数列。

(3)查找算法分析

平均查找长度(Average Search Length,ASL):需和指定key进行比较的关键字的个数的期望值,称为查找算法在查找成功时的平均查找长度。

对于含有n个数据元素的查找表,查找成功的平均查找长度为:ASL = Pi*Ci的和。

Pi:查找表中第i个数据元素的概率。

Ci:找到第i个数据元素时已经比较过的次数。

 

2.二分查找(折半查找)

(1)二分查找说明

元素必须是有序的,如果是无序的则要先进行排序操作。

(2)基本思想

二分查找也称为是折半查找,属于有序查找算法。用给定值k先与中间结点的关键字比较,中间结点把线形表分成两个子表,若相等则查找成功;若不相等,再根据k与该中间结点关键字的比较结果确定下一步查找哪个子表,这样递归进行,直到查找到或查找结束发现表中没有这样的结点。

(3)复杂度分析

最坏情况下,关键词比较次数为log2(n+1),且期望时间复杂度为O(log2n);

注:折半查找的前提条件是需要有序表顺序存储,对于静态查找表,一次排序后不再变化,折半查找能得到不错的效率。但对于需要频繁执行插入或删除操作的数据集来说,维护有序的排序会带来不小的工作量,那就不建议使用。——《大话数据结构》

(4)二分查找C语言源代码

(5)二分查找C++源代码

 

 

版权声明:本文著作权归原作者所有,欢迎分享本文,谢谢支持!
转载请注明:常用的7大查找算法之二:二分查找(折半查找) | 算法君

发表评论


表情