erlang - 在 lg(n) 时间内在 Erlang 中进行二进制搜索

Question

我正在寻找在 Erlang 中进行二进制搜索的可能解决方法，我发现 http://ruslanspivak.com/2007/08/15/my-erlang-binary-search/但我想知道博客中的解决方案是否在 O(lg n) 中运行。现在，由于二分搜索的递归是:T(n) = T(n/2) + c，这给了我 O(lg n) 的执行时间。

因为在 C 数组中，您可以在 O(1) 时间内访问任何元素。但是在 erlang 中，如果访问列表的中间需要 cn 时间，那么二进制搜索在线性总体时间中运行的时间与线性搜索一样差。

我遇到了 lists:nth/2 BIF 用于查找列表中的第 n 个项目，但我不确定它的执行时间。

任何意见 ？

Answer 1

在 Erlang 中有一些允许 O(1) 访问的数据结构:ETS 表、元组和二进制文件。

现在，它们都不适合二进制搜索。 ETS 表支持从一开始就进行搜索，否则，在返回结果时会将数据复制到您的进程中，这对于您的用例可能不是最佳的。

元组允许使用 element/2 进行 O(1) 访问，但是修改它们有一定的开销(这就是数组模块使用元组树的原因)。

然后你有二进制文件( <<1,2,3,4,5>> )，它允许类似于指针算术的东西，如下例所示:

1> Sorted = <<$a,$b,$c,$d,$e,$f,$g,$h>>.
<<"abcdefgh">>
2> <<_:3/binary, X:1/binary, _/binary>> = Sorted.
<<"abcdefgh">>
3> X.
<<"d">>

但是，在构建二进制文件时预测性能有点粗略，如果您的值在二进制文件中表示时具有不同的类型和不同的大小，则这种指针算法更难进行。

您最好的选择可能是使用值列表，对其进行排序，然后使用 list_to_tuple/1使用 element/2 浏览它.

但是，我强烈建议您使用树进行搜索；使用 gb_tree 可能要简单得多。模块来构建平衡树并且仍然获得 O(log N) 搜索。