java - 一般: Search time in algorithm

Question

我有一个一般性问题(取自一些计算机科学测试)我想得到解释，问题是:

给定特定大小的排序数组，并假设我们使用计算机科学中最快的方法来查找数组中的值。在该方法中，任意元素的搜索时间不超过N秒。现在我们乘以数组的大小。数组中任意元素的搜索时间最多为:

答案:N+1。

任何人都可以给我一个完整的解释为什么这是答案吗？为什么不是 2*N ？

谢谢。

Answer 1

我认为“在这个方法中，任何元素的搜索时间不超过N秒”这句话只是为了迷惑你。

我将忽略秒并将其视为 O(N) 步骤。

有一种算法可以在 log(x) 步中查找元素(二分搜索 - 请参阅其他答案)。所以

log2(x) = N

log2(2*x) = N+1

(我知道这不是很精确和正式，但我希望您明白)。