查找算法的二分查找

 我来答
TK1McS
2016-06-01 · TA获得超过167个赞
知道答主
回答量:198
采纳率:50%
帮助的人:116万
展开全部

二分查找又称折半查找,它是一种效率较高的查找方法。
  【二分查找要求】:1.必须采用顺序存储结构2.必须按关键字大小有序排列。
【优缺点】折半查找法的优点是比较次数少,查找速度快,平均性能好;其缺点是要求待查表为有序表,且插入删除困难。因此,折半查找方法适用于不经常变动而查找频繁的有序列表。  【算法思想】首先,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功;否则利用中间位置记录将表分成前、后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表。  重复以上过程,直到找到满足条件的记录,使查找成功,或直到子表不存在为止,此时查找不成功。  【算法复杂度】假设其数组长度为n,其算法复杂度为o(log(n))
  下面提供一段二分查找实现的伪代码:
BinarySearch(max,min,des)
mid-des then  max=mid-1  else  min=mid+1  return max
  折半查找法也称为二分查找法,它充分利用了元素间的次序关系,采用分治策略,可在最坏的情况下用O(log n)完成搜索任务。它的基本思想是,将n个元素分成个数大致相同的两半,取a[n/2]与欲查找的x作比较,如果x=a[n/2]则找到x,算法终止。如 果xa[n/2],则我们只要在数组a的右 半部继续搜索x。

已赞过 已踩过<
你对这个回答的评价是?
评论 收起
迈杰
2024-11-30 广告
GWAS,即全基因组关联分析,是一种强大的遗传学研究方法。它通过对大规模群体的DNA变异进行系统性扫描,寻找与特定性状(如疾病易感性、药物反应等)相关联的遗传变异。在迈杰转化医学研究(苏州)有限公司,我们利用先进的GWAS技术,挖掘疾病相关... 点击进入详情页
本回答由迈杰提供
推荐律师服务: 若未解决您的问题,请您详细描述您的问题,通过百度律临进行免费专业咨询

为你推荐:

下载百度知道APP,抢鲜体验
使用百度知道APP,立即抢鲜体验。你的手机镜头里或许有别人想知道的答案。
扫描二维码下载
×

类别

我们会通过消息、邮箱等方式尽快将举报结果通知您。

说明

0/200

提交
取消

辅 助

模 式