首页 > 试题广场 >

使用二分搜索算法在 1000 个有序元素表中搜索一个

[单选题]

使用二分搜索算法在 1000 个有序元素表中搜索一个特定元素,在最坏情况下,搜索总共需要比较的次数为( )。

  • 10
  • 11
  • 500
  • 1000

如果把顺序表的序号(下标)变成二叉树的话,根节点为初始值的mid(low+height/2)左子树为左子表,右子树为右子表,以此类推完成一个判断树(完全二叉树)

会发现二分查找的过程实际上就是由根节点到某个节点的路径,最大路径不会超过其深度。

完全二叉树在由n个节点的情况下最大深度为(log2n)+1

题目就是(log2 1000)+1 约等于10

发表于 2019-08-13 23:37:24 回复(0)
二分搜索的时间复杂度是:
O(log2 n)如果是整数,则就是这个数,如果不是整数,那么就取下线然后再加1
  
发表于 2017-09-25 20:50:10 回复(1)
至多比较次数是⌊log2(n)⌋+1,其中⌊ ⌋表示向下取整
发表于 2017-09-11 10:15:37 回复(1)
2^10近似等于1024,所以最坏情况下需要执行10次
发表于 2020-03-10 09:00:57 回复(1)

最多比较次数log2n向下取整+1

发表于 2019-12-08 23:54:06 回复(0)
我太傻了,随便举个例子也不会这样啊。
发表于 2020-05-21 17:56:47 回复(0)
我以为查的数不在数组内,也就是10+1。。。。理解错了。。
发表于 2018-04-02 14:51:56 回复(3)
次数至多是Log2 n+1
发表于 2021-07-29 23:46:20 回复(0)
对于二分查找,查找成功与查找不成功,最坏的情况下,都需要比较[log2n]+1(向下取整),或者[log2(n+1)](向上取整),其实就是树的深度公式
发表于 2021-07-16 14:20:49 回复(0)
即完全二叉树的深度[log2n]+1,其中[]为向下取整
发表于 2021-05-03 16:29:29 回复(0)
深度为10的完全二叉树,节点数总数为210-1 = 1023;
如果深度为9,则节点总数为29-1 = 511;
所以题中1000个节点的二叉树深度为10,最坏情况需要查找10次。
发表于 2020-07-03 08:35:30 回复(0)
<p>最多次数Log2 (n)向下取整➕1</p>
发表于 2020-06-19 15:52:36 回复(0)
二分的时间复杂度为log2 n 加1
发表于 2020-06-08 20:23:50 回复(0)
2的10次方为1024
发表于 2019-02-19 19:35:28 回复(0)