algorithm - 对未排序数组进行二分搜索？

Question

我遇到了这个文档Binary Search Revisited，作者已经证明/解释了二进制搜索也可以用于未排序的数组（列表）。在第一次阅读时，我并没有深入了解该文件的大部分内容。

你们中有人已经探索过这个吗？

Answer 1

我刚刚读过报纸。对我来说，作者使用术语二分搜索来解决用于查找连续函数零点的二分法。

论文中的示例显然受到了一些问题的启发，例如在区间中找到零（在 y 轴上平移）或在表格数据中找到函数的最大值/最小值。

本文考虑的数组不是随机填充的，您会找到构造它们的规则（这是与用于转储它们的函数相关联的规则）

说这是一个很好的机会来修补属于一个共同家族的不同算法，以便找到相似之处和不同之处。扩展您的经验的好机会。

绝对不是一个新概念或被低估的概念。

Answer 2

使用 binary 或 bisection 在该未排序列表中查找 3 ：

L = 1 5 2 9 38 11 3

1-取整个列表的中点 L : 9 3 < 9 所以删除列表的右边部分 (38 11 3) 在这里你已经可以理解你永远找不到 3

2-在剩余列表中取中点 1 5 2 : 5 3 > 5 所以删除列表的右侧部分 (5 2) 仍然是 1

结果 : 3 未找到

两个备注：

1-二进制或二等分算法将左右视为顺序的指示所以我粗鲁地应用了通常的算法，考虑到右高左低如果你考虑相反的情况，即右低左高，那么，试图在这个稍微相似的列表中找到 3 将导致“3 未找到”L' = L = 1 5 2 9 3 38 11 3 < 9 / 正确部分：3 38 11 中点 38 3 < 38 正确部分：11 3 未找到

2-如果您接受系统地在列表的已删除部分上重新应用该算法，那么它会导致在 n 个元素的列表中搜索元素复杂性将是 O(n) 与从请求到结束运行所有列表完全相同搜索您的价值。搜索时间可能会稍微短一些。为什么 ？让我们考虑一下您从乞讨中一一看。以排序列表中的值 100000 结束。您将在列表末尾找到它！:-)

如果现在这个列表是无序的并且你的值 100000 正好在中间点......宾果！

Answer 3

可以在旋转的未排序数组/列表上实现二进制搜索。