给定一个数组部分是不是排序部分，如何找到一个特定的元素？

Question

说实话，这是一个面试问题。我知道如果数组完全排序，那么我可以使用二进制搜索，这是O（logN）。但现在的条件是：

1. 某些部分是排序而其他部分不是。
2. 我们不知道哪一部分是排序的，也不知道这部分是多长时间。

我只能想到一个完整的阵列扫描解决方案，它是O（N）。但采访者说有一个O（logN）解决方案。请帮忙。

Answer 1

面试官是错的。不知道排序部分的起始位置及其大小，无法在O（logN）中搜索它。

Answer 2

要么你没有讲完整个问题，要么你的面试官完全错了。这里有一个适合你的描述的例子。

[1, 2, 3, 4, 5, 9, -1, 8, 0, 8, -2, 4, 7, 6]

正如你看到的第5个元素进行排序。但它不能帮助你找到我的阵列中的6个位置。您仍然需要O（n）来查找元素。

把你的问题提到一个极端，如果排序部分包含2个元素和未排序部分是n-2元素？他还可以在O(log n)中搜索吗？

只是一个建议给你。一旦你听到一些你实际上不能相信的东西，请一个人向你解释一个想法，并想一个使这个想法无用的反例。