我要投搞

标签云

收藏小站

爱尚经典语录、名言、句子、散文、日志、唯美图片

当前位置:爱彩网 > 二分搜索 >

java 线性查找和二分查找的区别

归档日期:07-01       文本归类:二分搜索      文章编辑:爱尚语录

  定义:在一列给定的值中进行搜索,从一端开始逐一检查每个元素,直到找到所需元素的过程。

  线性查找又称为顺序查找。如果查找池是某种类型的一个表,比如一个数组,简单的查找方法是从表头开始,一次将每一个值与目标元素进行比较。最后,或者查找到目标,或者达到表尾,而目标不存在于组中,这个方法称为线性查找。

  【二分查找要求】:1.必须采用顺序存储结构 2.必须按关键字大小有序排列。

  【优缺点】折半查找法的优点是比较次数少,查找速度快,平均性能好;其缺点是要求待查表为有序表,且插入删除困难。因此,折半查找方法适用于不经常变动而查找频繁的有序列表。

  【算法思想】首先,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功;否则利用中间位置记录将表分成前、后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表。

  重复以上过程,直到找到满足条件的记录,使查找成功,或直到子表不存在为止,此时查找不成功。

  折半查找法也称为二分查找法,它充分利用了元素间的次序关系,采用分治策略,可在最坏的情况下用O(log n)完成搜索任务。它的基本思想是,将n个元素分成个数大致相同的两半,取a[n/2]与欲查找的x作比较,如果x=a[n/2]则找到x,算法终止。如 果xa[n/2],则我们只要在数组a的左半部继续搜索x(这里假设数组元素呈升序排列)。如果xa[n/2],则我们只要在数组a的右 半部继续搜索x。

本文链接:http://pikeducation.com/erfensousuo/458.html