二分搜索对于均匀分布非常有效。您列表中的每个成员都有相同的“命中”概率。这就是您每次都尝试中心的原因。
对于非均匀分布是否有有效的算法？例如服从 1/x 分布的分布。
最佳答案
二叉搜索和二叉树之间有着深刻的联系——二叉树基本上是一种“预先计算”的二叉搜索，其中切割点由树的结构决定，而不是在搜索运行时选择。事实证明，处理每个键的概率“权重”有时是用二叉树完成的。
一个原因是因为它是一棵相当普通的二叉搜索树，但事先已知，包含查询概率的知识。
Niklaus Wirth 在他的“算法和数据结构”一书中介绍了这一点，有几种变体(一种用于 Pascal，一种用于 Modula 2，一种用于 Oberon)，至少可以从他的 web site 下载其中一种。 .
不过，二叉树并不总是二叉搜索树，二叉树的一种用途是派生 Huffman compression code .
无论哪种方式，二叉树的构建都是从叶子分开开始，然后在每一步中将两个最不可能的子树连接成一个更大的子树，直到只剩下一个子树。为了在每一步有效地挑选出两个最不可能的子树，使用了一个优先级队列数据结构——可能是一个binary heap。 .
一棵构建一次就永远不会修改的二叉树可以有多种用途，但是可以有效更新的二叉树更有用。那里有一些权重平衡的二叉树数据结构，但我不熟悉它们。当心 - 术语“权重平衡”通常用于每个节点始终具有权重 1，但子树权重大致平衡的情况。其中一些可能适用于不同的节点权重，但我不确定。
无论如何，对于数组中的二分查找，问题是可以使用任意概率分布，但效率低下。例如，您可以有一个运行总权重数组。对于二分搜索的每次迭代，您想要确定概率分布点的一半，因此您确定其值然后搜索运行总权重数组。您为主要二分搜索获得了完美的权重平衡的下一个选择，但您必须对正在运行的总数组进行完整的二分搜索才能做到这一点。
但是，如果您可以在不搜索已知概率分布的情况下确定加权中点，则该原则有效。原理是一样的——你需要概率分布的积分(替换运行总数组)，当你需要一个中点时，你可以选择它来获得积分的精确中心值。这与其说是编程问题，不如说是代数问题。
像这样的加权二分搜索的一个问题是最坏情况下的性能更差 - 通常是常数因子，但如果分布足够偏斜，您可能最终会得到有效的线性搜索。如果您假设的分布是正确的，尽管搜索偶尔会很慢，但平均情况下的性能会得到改善，但如果您的假设分布是错误的，那么当许多搜索是针对根据该分布不太可能出现的项目时，您可能会为此付出代价。在二叉树形式中，“不太可能”的节点比它们在简单平衡(假设平坦概率分布)二叉树中离根更远。
平坦概率分布假设即使在完全错误的情况下也能很好地发挥作用 - 最坏的情况是好的，而最好的和平均的情况必须至少按照定义那么好。您离平坦分布越远，如果实际查询概率与您的假设大相径庭，情况就会越糟。
关于performance - 不均匀分布的二进制搜索，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/16872675/