二分查找也称折半查找(BinarySearch),它是一种效率较高的查找方法。但是,折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列。
查找过程
首先,假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功;否则利用中间位置记录将表分成前、后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表。重复以上过程,直到找到满足条件的记录,使查找成功,或直到子表不存在为止,此时查找不成功。
算法要求
1。必须采用顺序存储结构。
2。必须按关键字大小有序排列。
比较次数
计算公式:
当顺序表有n个关键字时:
查找失败时,至少比较a次关键字;查找成功时,最多比较关键字次数是b。
注意:a,b,n均为正整数。
算法复杂度
二分查找的基本思想是将n个元素分成大致相等的两部分,取a〔n2〕与x做比较,如果xa〔n2〕,则找到x,算法中止;如果xa〔n2〕,则只要在数组a的左半部分继续搜索x,如果xa〔n2〕,则只要在数组a的右半部搜索x。
时间复杂度无非就是while循环的次数!
总共有n个元素,
渐渐跟下去就是n,n2,n4,。。。。n2k(接下来操作元素的剩余个数),其中k就是循环的次数
由于你n2k取整后1
即令n2k1
可得klog2n,(是以2为底,n的对数)
所以时间复杂度可以表示O(h)O(log2n)
下面提供一段二分查找实现的伪代码:
BinarySearch(max,min,des)
mid(maxmin)2
while(mindesthen
maxmid1
else
minmid1
returnmax
折...
(全文)