在二进制搜索中，为什么不首先检查要搜索的元素是否小于或大于数组的最小或最大索引？

Question

进行二进制搜索时，我们将对数组的搜索范围逐步划分为一半，并寻找所需元素。如果排序数组中不存在该元素，则仅在将数组的最后一个剩余元素与之进行比较之后才能得到结果。为什么不使用简单的语句，如：

def binarySearch(array,element):
        maxIndex=len(array)-1

       if(array[maxIndex]<element):
                return -1
       if(array[0]>element):
                return -1

[基本上，为什么不先与已排序数组的最小值和最大值进行比较，以检查数组中元素的存在。

它甚至可能甚至不存在于数组中，但是如果元素大于或小于数组的任何元素，我们仍然节省了大量搜索。

Answer 1

在二进制搜索中，比较的次数约为1 + log ₂ n，假设一种算法每次迭代仅执行一次比较（因此不进行相等性检查），并且进行最后一次比较以查看是否只有剩余的候选者值是一个匹配项。

如果确实搜索到的值超出了数据集的外部限制，那么您的建议会将比较次数减少到1或2（取决于离群值在哪一边-假设概率是均匀分布的）。不利的一面是，对于小于或等于这些限制的值，现在您将比较的数量<2增加了<2。因此，可能会发现，在average上，您实际上损失的多于所获得的。这取决于获得搜索值在限制范围内（不一定是匹配项）的可能性。让我们打电话P获得

outside

边界的值的概率。如果该概率很高，则平均比较次数将低于标准算法。但是，如果概率不够高，则平均比较次数将高于标准算法。如果您既知道所涉及的概率，又知道二叉树的大小，则可以根据简单的算术公式来确定这两种算法中哪一种最好：

标准算法：

1 + log
• 2

n预期比较您的建议：* 1.5 * P +（1-P）（3 + log

2

n）预期比较。请注意3，其中包括2个额外的比较。因此只需插入n和

P的实际值，就可以检查哪种算法平均只会执行较少的比较。