推广 热搜: 行业  机械  设备    系统  教师  经纪  参数    蒸汽 

二分查找算法

   日期:2024-11-10     移动:http://changmeillh.xhstdz.com/mobile/quote/3979.html

枚举查找也就是顺序查找。

二分查找算法

实现原理就是逐个比较 a[0:n-1] 中的元素,直到找出元素 x 或搜索遍整个数组后确定 x 不在其中,或者说符合要求的元素在不在数组中。

最坏的情况下需要比较 N 次,时间复杂度是 O(n) 线性阶。

二分查找也就是折半查找。折半查找是将 N 个元素分成大致相同的两部分。选取中间元素与查找的元素比较,或者与查找条件相比较,找到或者说找到下一次查找的半区。每次都将范围缩小至1/2​ 所以时间复杂度是 O(log2n),但是二分查找的前提是有序,一般是从小到大排列。且一般用于查<=x的max值>=x的min值。

折半查找的基本思想:

在有序表中(low,high,low<=high),取中间记录即 [(high+low)/2] 作为比较对象。

  • 若给定值与中间记录的关键码相等,则查找成功
  • 若给定值小于中间记录的关键码,则在中间记录的左半区继续查找
  • 若给定值大于中间记录的关键码,则在中间记录的右半区继续查找

不断重复上述过程,直到查找成功,或所查找的区域无记录,查找失败。

二分查找的特征:

  1. 答案具有单调性;
  2. 二分答案的问题往往有固定的问法,比如:令最大值最小(最小值最大),求满足条件的最大(小)值等。

折半查找一般过程:

本文地址:http://changmeillh.xhstdz.com/quote/3979.html    物流园资讯网 http://changmeillh.xhstdz.com/ , 查看更多

特别提示:本信息由相关用户自行提供,真实性未证实,仅供参考。请谨慎采用,风险自负。


0相关评论
相关最新动态
推荐最新动态
点击排行
网站首页  |  关于我们  |  联系方式  |  使用协议  |  版权隐私  |  网站地图  |  排名推广  |  广告服务  |  积分换礼  |  网站留言  |  RSS订阅  |  违规举报  |  鄂ICP备2020018471号