是的，二进制搜索是最佳选择。

通过诉诸信息论，很容易看出这一点。它log N仅需要位来 标识 元素中的唯一N元素。但是每次比较只给您一点信息。因此，您必须执行log N比较以识别唯一元素。

更详细地讲…考虑在最坏的情况下优于二进制搜索的假设算法X。对于数组的特定元素，运行算法并 记录
其提出的问题；即它执行的比较顺序。或者，记录这些问题的 答案 （例如“ true，false，false，true”）。

将该序列转换为二进制字符串（1,0,0,1）。将该二进制字符串称为“元素相对于算法X的签名”。对数组的每个元素执行此操作，为每个元素分配一个“签名”。

现在这里是关键。如果两个元素具有相同的签名，则算法X无法区分它们！该算法知道的所有关于数组的信息都是从其提出的问题中得到的答案。即它执行的比较。而且，如果该算法无法将两个元素区分开，那么它就不会正确。（换句话说，如果两个元素具有相同的签名，则意味着它们导致算法产生相同的比较序列，该算法返回哪一个？矛盾。）

最后，证明如果每个签名的log N位数都少于位，那么必须存在两个具有相同签名的元素（鸽子洞原理）。做完了

[更新]

快速补充说明。以上假设算法除了从执行比较中学到的知识外，对数组一无所知。当然，在现实生活中，有时候您确实对 先验
数组有所了解。作为一个玩具示例，如果我知道该数组具有（例如）10个元素，它们都在1到100之间，并且它们是不同的，并且数组中存在数字92到100
…那么显然我不即使在最坏的情况下也需要执行四个比较。

更现实的是，如果我知道元素的最小值和最大值之间是均匀分布的（或大致均匀分布的），那么我可以做得比二进制搜索更好。

但是在一般情况下，二进制搜索仍然是最佳的。