我要招人

去企业版

首页 > 试题广场 >

设有序顺序表中有n个数据元素，则利用二分查找法查找数据元素X

[单选题]

设有序顺序表中有n个数据元素，则利用二分查找法查找数据元素X的最多比较次数不超过（）。

```
log2n+1
```
```
log2n-1
```
```
log2n
```
```
log2(n+1)
```

查看答案及解析

hahahha123

因为二分查找每次排除掉一半的不适合值，所以对于n个元素的情况：
一次二分剩下：n/2
两次二分剩下：n/2/2 = n/4
。。。
m次二分剩下：n/(2^m)
在最坏情况下是在排除到只剩下最后一个值之后得到结果，所以为
n/(2^m)=1;

2^m=n;

此时时间复杂度为log2（n）

再与最后一个元素比较复杂度+1

所以时间复杂度为：log2(n)+1

发表于 2017-11-22 16:48:06 回复(2)

孙强Jimmy

选项应该是这样的吧：

A.log₂n+1

B.log₂n-1

C.log₂n

D.log₂(n+1)

发表于 2017-07-27 09:14:13 回复(6)

夜悊

应该是：

log2n下取整+1

log2(n+1)上取整

发表于 2022-11-01 15:03:22 回复(0)

新鲜的菜鸟

每次比较剩一半，所以log2n，极端情况n等于1，要比较一次，log2n等于0，。所以答案log2n+1

发表于 2019-11-20 09:18:33 回复(0)

葬爱家族小鑫鑫

这道题我不知道该怎么说，学计算机的都应该有常识，从来都是log代替log2。现在这里这么写，我是不是可以认为是log2（2n）+ 1.

发表于 2019-04-25 16:55:15 回复(2)

为你扣下F键

其实就是算n个结点的完全二叉树高度

发表于 2018-09-05 12:37:40 回复(1)

爱吃青菜皮卷面的byr

log2n万一算出来是3.4。其实是比较4次啊，但是不会超过4.4次

发表于 2017-07-15 18:37:50 回复(0)

刷了100道题的灰太狼很想养修勾

可能这人写不出二为底，向下取整向上取整也不搞一下

发表于 2023-03-28 20:18:17 回复(0)

牛客321509759号

这下标写法真害人，

发表于 2023-06-13 11:47:28 回复(0)

牛客801282807号

排版真的有问题

发表于 2022-08-09 12:51:10 回复(0)

aiprogram

这种题目就是缺少一个Latex的数学公式输出功能，导致歧义出现。牛客网针对程序员，加强数学公式显示这方面咋不重视呢。

发表于 2020-08-01 10:10:10 回复(0)

牛客818246740号

<p>自己本身一次</p>

发表于 2020-07-01 11:57:38 回复(0)

JIANRU啊

选项这种写法有问题吧，一般我们写复杂度时都是直接省略log的底的，就算写出来也不是这么个写法，是那位大佬出的题，改一下吧

发表于 2020-04-20 11:34:18 回复(0)

邓胜涛1

二分，左右查，最后找到

发表于 2019-01-05 10:07:19 回复(0)

提交观点

问题信息

查找

上传者：阿奻_

难度：

14条回答 594收藏 16594浏览

设有序顺序表中有n个数据元素，则利用二分查找法查找数据元素X

可能这人写不出二为底，向下取整向上取整也不搞一下

问题信息

热门推荐

相关试题