请问各位，有序数组中如何寻找某一特定值，除了二分以外的算法，有类似的时间复杂度？

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

已注册用户请登录

这是一个创建于 1105 天前的主题，其中的信息可能已经有所发展或是发生改变。

碰到这个问题，一头雾水

9 条回复 • 2021-04-16 21:46:46 +08:00

uselessVisitor

2021-04-15 21:32:44 +08:00

当然是哈希表啦

abersheeran

2021-04-15 22:22:45 +08:00

跳表。

suiterchik

2021-04-15 22:25:08 +08:00

如果数据结构限定为有序数组，那么对数据分布无先验信息的情况下，二分查找应该是效率最高的
如果有先验的话，可以将二分查找改进为插值查找或者斐波那契查找

raaaaaar

2021-04-15 22:25:19 +08:00 via Android

都有序数组了还 HASH 啥，二分挺快了呀，为什么不用

ch2

2021-04-15 22:42:55 +08:00

茴字几种写法？将来当面试官的时候装逼要用？

ipwx

2021-04-15 23:02:04 +08:00

虽然二分查找和很多其他算法一样都是 O(log N)，但是它常数很无敌的。。。

除非你的需求是多次查找，可能会有均摊小于 O(log N) 的辅助数据结构。

thedrwu

2021-04-16 00:33:21 +08:00 via Android

三分

tyroshu

2021-04-16 17:02:45 +08:00

@ch2 是被面试官问到了。。。。

tyroshu

2021-04-16 21:46:46 +08:00

@suiterchik 感谢大佬