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

[tyroshu]

碰到这个问题，一头雾水

[zm8m93Q1e5otOC69]

当然是哈希表啦

[abersheeran]

跳表。

[JensenQi]

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

[raaaaaar]

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

[ch2]

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

[ipwx]

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

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

[thedrwu]

三分

[tyroshu]

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

[tyroshu]

@suiterchik 感谢大佬