相关动态
二分查找算法
2024-11-10 16:16

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

二分查找算法

实现原理就是逐个比较 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://mip.xhstdz.com/quote/3979.html 
     栏目首页      相关文章      动态      同类文章      热门文章      网站地图      返回首页 物流园资讯移动站 http://mip.xhstdz.com/mobile/ , 查看更多   
发表评论
0评