algorithm - 是否存在利用已知可搜索值分布的搜索算法？

Question

例如，我有一个从 1 到 10 的值列表。这些值位于排序数组中。由于我知道上限、下限、中位数、均值...等，并且这些值是有序的，所以没有一种算法可以利用这些知识并提供快速有效的搜索特殊价值？

Answer 1

绝对地。

对于任何形式的具有 O(logn) 复杂度的分而治之算法来说，这听起来都是一个很好的候选者（您将每一步的问题空间减半）。

查看http://en.wikipedia.org/wiki/Binary_search_algorithm#Algorithm并以您选择的语言实现。

Java（二进制搜索）：http ://docs.oracle.com/javase/7/docs/api/index.html

Python（二等分）：http ://docs.python.org/library/bisect.html

希望这可以帮助。
埃德蒙