首页 > 试题广场 >

用二分法查找长度为10的、排好序的线性表,查找不成功时,最多

[单选题]
用二分法查找长度为10的、排好序的线性表,查找不成功时,最多需要比较多少次?
  • 3
  • 4
  • 5
  • 6
二分查找,可以用二叉判定树,查找不成功的次数不超过判定树的深度,即(log2n)+1,其中log2n向下取整。
发表于 2020-06-22 15:21:05 回复(0)
二分查找,可以用二叉判定树,查找不成功的次数不超过判定树的深度,即(log2n)+1,其中log2n向下取整。

欢迎各位关注在下的微信公众号“张氏文画”,不光有新鲜的 LeetCode 题解,还有经典的文章及短视频和大家分享,一起嘿嘿嘿

编辑于 2020-03-26 16:06:47 回复(0)
二分查找类似于二叉树每层顶点的个数,2**3 =8 2**4 = 16 显然 8 <10 <16,取上整,所以等于4
发表于 2018-09-22 22:21:43 回复(0)
二分查找,可以用二叉判定树,查找不成功的次数不超过判定树的深度,而树的深度为|_log2n_|+1
发表于 2017-10-23 08:33:54 回复(0)
B  两种思路,一个是二叉判定树,另一个是根据二分法的算法。
发表于 2017-10-30 10:12:01 回复(0)
二分查找,可以用二叉判定树,查找不成功的次数不超过判定树的深度,即(log2n)+1,其中log2n向下取整。
发表于 2021-03-10 16:33:59 回复(0)
第一种:1到10,查找0,第一次比较的是下标为 (0+9)/2=4 的元素5,第二次比较的是下标为 (0+3)/2=1 的元素2,第三次比较的是下标为 (0+0)/2=0 的元素1,算法结束,共比较3次。
第二种:1到10,查找11,第一次比较的是下标为 (0+9)/2=4 的元素14,第二次比较的是下标为 (5+9)/2=7 的元素17,第三次比较的是下标为 (8+9)/2=8 的元素18,第四次比较的是下标为 (9+9)/2=9 的元素19,算法结束,共比较4次。
所以最多为4次。
发表于 2019-07-22 11:28:07 回复(0)