使用二分搜索算法在 1000 个有序元素表中搜索一个特定元素,在最坏情况下,搜索总共需要比较的次数为( )。
10
11
500
1000
如果把顺序表的序号(下标)变成二叉树的话,根节点为初始值的mid(low+height/2)左子树为左子表,右子树为右子表,以此类推完成一个判断树(完全二叉树)
会发现二分查找的过程实际上就是由根节点到某个节点的路径,最大路径不会超过其深度。
完全二叉树在由n个节点的情况下最大深度为(log2n)+1
题目就是(log2 1000)+1 约等于10
最多比较次数log2n向下取整+1
这道题你会答吗?花几分钟告诉大家答案吧!
扫描二维码,关注牛客网
下载牛客APP,随时随地刷题