1. CMS首页
  2. 技术杂文

C语言代码浅析对分查找算法和最多判断次数

  初学查找常用的就是对分查找和顺序查找,因为顺序查找通常是最粗糙的一种查找方式,今天猴大大来浅析下对分查找。

  算法的原理是定义边界左0,右n,通常用数组实现,n为数组最后一个下标。假定数组元素从小到大排序(对分查找的前提是数据有序)左右下标除2取得数组中间的数字(如果不是恰好中间会取左边一个,因为整除舍弃了小数)如果中间值小于目标值,则右界=中间位置-1,否则左界=中间位置 1。

  对于判断次数问题,其实就是看数组成员数能被2乘几次,因为整除舍小数原因,在过程中如果出现中间位置不是恰好中间那个数的情况,会偏向左边,所以如果目标值在第一次mid的左边比目标值在mid右边小1(如果目标值不在所查找数据中也一样成立)。用log2(n) (2是底数,n为真数)来表示n个数字最多能被2除几次,而对分查找最多的次数就是目标值在第一次mid的右边的情况,最多次数max=log2(n) 1。

  代码附上 C语言:


发表评论

用户名: