手机

当前位置:查字典资讯网 > 考试 > 2015年计算机二级公共基础知识复习知识点(7)

2015年计算机二级公共基础知识复习知识点(7)

来自:查字典教育资讯网 2015-10-22

  二分法查找

二分查找只适用于顺序存储的有序表。此处所述的有序表是指线性中的元素按值非递减排列(即由小到大,但允许相邻元素值相等)。

二分查找的方法如下:

将要查找的元素与有序序列的中间元素进行比较:

如果该元素比中间元素大,则继续在线性表的后半部分(中间项以后的部分)进行查找

如果要查找的元素的值比中间元素的值小,则继续在线性表的前半部分(中间项以前的部分)进行查找

这个查找过程一直按相同的顺序进行下去,一直到查找成功或子表长度为0(说明线性表中没有要查找的元素)

有序线性表的二分法查找,条件是必须这个有序线性表的存储方式是顺序存储的。它的查找效率比顺序查找要高得多,它的最坏情况的查找次数是log2n次,而顺序查找的最坏情况的查找次数是n次。

当然,二分查找的方法也支持顺序存储的递减序列的线性表。

有非递减有序线性表:1、2、4、5、7、9,要查找元素6。查找的方法是:

序列长度为n=6,中间元素的序号m=[(n+1)/2]=3

查找计次k=1,将元素6与中间元素即元素4进行比较,不等,64

查找计次k=2,查找继续在后半部分进行,后半部分子表的长度为3,计算中间元素的序号:m=3+[(3+1)/2]=5,将元素与后半部分的中间项进行比较,即第5个元素中的7进行比较,不等,6<7

查找计次k=3,继续查找在后半部分序列的前半部分子序列中查找,子表长度为1,则中间项序号即为m=3+[(1+1)/2]=4,即与第4个元素5进行比较,不相等,继续查找的子表长度为0,则查找结束

更多精彩资讯请关注查字典资讯网,我们将持续为您更新最新资讯!

上一篇:2015年福建福州中考满分作文:让未来记... 下一篇:留学选校看排名or 就业?近50%中国学...