搜索数组中元素的算法

Question

这是另一个面试问题

数组包含元素，如果前一个元素是 x，则下一个元素可以是 x+1 或 x-1。

Prev element = x
Next element = x+1/ x-1

示例:{2, 3, 4, 3, 2, 1, 0, -1, 0, 1, 2, 3, 2, 1}

如果我需要搜索 0，我们可以选择什么最佳算法？

如果我对它进行排序，那么它将是 O(nlogn)，我可以在 O(n) 中遍历数组，所以 O(n) 仍然更好

创建二叉搜索树将再次是 O(n)，在 BST 中搜索是 O(log)，所以仍然是 O(n)。

它是一个随机数组，下一个元素是 +1 或 -1 不会导致任何搜索模式。 如果你们能想到可以在此处使用的任何搜索模式来执行更好的搜索，请告诉我。

Answer 1

显而易见的事情是:

1. 考虑第一个值，假设该值为 n。是 0 吗？
2. 如果是，您就完成了。
3. 如果不是，则向前走abs(n)个元素，转步骤1。

您可以跨过多个元素，因为两个相邻值之间的绝对差始终为 1。

因此，鉴于您问题中的数组，您执行以下操作:

• 项目 0 是 2。它不是零，因此您转到项目 2。
• 第 2 项是 4。这不是零，向前移动 4 项到第 6 项。
• 第 6 项是 0。你完成了。