我要招人

去企业版

首页 > 试题广场 >

一个长度为 n 的正整数数列，先递减再递增，如果要找到数列中

[单选题]

一个长度为 n 的正整数数列，先递减再递增，如果要找到数列中最小的正整数，最优算法的平均时间复杂度是？

```
O(n)
```
```
O(nlog(n))
```
```
O(n^2)
```
```
O(log(n))
```

查看正确选项

emiedon

二分法找中点，中点左右两边数都比中点大就结束，否则就向较低的一边搜索

发表于 2019-04-15 20:15:44 回复(3)

yaqin123

二分法

发表于 2019-04-03 23:17:07 回复(0)

onsix

根据big-O notation 的定义，C和D两个选项不是等价的吗？

发表于 2019-06-01 13:56:25 回复(1)

牛客507236609号

折半查找法,平均时间复杂度O(logn)

发表于 2021-05-29 10:08:45 回复(0)

Tencent首席架构师

二分法要求数组有序，这种情况怎么二分？

发表于 2023-05-11 23:22:06 回复(0)

ksdeer

不考虑线段树的建树复杂度，查询复杂度是O（logn）

发表于 2021-03-29 00:20:30 回复(0)

春江鸭先知

二分法，左右两边比较，如果小于就左区间找，大于就右区间找，等于就左或者又循环找直到小于或大于，如果找到边界要注意判断数组越界

发表于 2021-02-06 09:43:33 回复(0)

乘湘去

发表于 2019-11-23 21:03:50 回复(0)

offer！快到我碗里来！

先减后增找最小，说二分法的可以分给我看看嘛

发表于 2019-05-29 21:27:11 回复(0)

胡卫201904241745308

感觉有点问题，因为每次要跟左右两边都比较一次。每次比两次，然后二分法下来大概要log n 次，所以是 2*log(n) = log(n^2)。实际上，用大O语言，log(n^2) 和 log(n) 是一个意思呀。。

发表于 2019-04-24 20:56:56 回复(1)

Better-M

这个题，我在想，用堆行不行呢，我们知道，将新来的元素插入堆中的时间复杂度是log(i-1)，其中i-1是当前元素的之前的(i-1)个元素；所以建堆的时间复杂度是，log1+log2+log3+.....log(n-1)=-------O(n)----------!!!!!即建堆的时间复杂度是线性的。但是我们的答案里有更小的log(n)，于是我在想，有没有更快的方法呢？答案是有：即二分法，二分法的时间复杂度就认为是logn即可，虽然在这里使用二分法，我没搞明白不是完全有序，我该怎么用。

发表于 2019-04-13 16:10:07 回复(2)

提交观点

问题信息

复杂度

来自：创新工场DeeCamp...

上传者：小小

难度：

11条回答 182收藏 8292浏览

一个长度为 n 的正整数数列，先递减再递增，如果要找到数列中

问题信息

热门推荐

相关试题