我已阅读以下内容：https : //www.topcoder.com/community/competitive-programming/tutorials/binary-search。我听不懂某些部分==>
我们可以称其为主要定理的条件是，当且仅当对于S中的所有x，对于所有y> x，p（x）都意味着p（y）时，才可以使用二进制搜索。当我们丢弃搜索空间的后半部分时，将使用此属性。等效地说，对于所有y <x，¬p（x）都意味着¬p（y）（符号¬表示逻辑非运算符），这是我们在丢弃搜索空间的前一半时所使用的。
但是我认为当我们要在数组中查找元素（仅检查是否相等）时此条件不成立，并且仅当我们尝试查找不等式时（例如，当我们搜索更大或相等的元素时），此条件才成立达到我们的目标值。
示例：我们在此数组中找到5。
索引= 0 1 2 3 4 5 6 7 8
1 3 4 4 5 6 7 8 9
我们定义p（x）=>
if(a[x]==5) return true else return false
步骤一=>中间索引= 8 + 1/2 = 9/2 = 4 ==> a [4] = 5并且p（x）对此是正确的，并且根据主要理论，结果是p（x + 1）........ p（n）是正确的，但事实并非如此。
那是什么问题呢？
我们可以在寻找精确值时使用该定理，因为我们
仅在丢弃一半时使用它。如果我们正在寻找说5，
而我们在中间发现说6，则可以丢弃上半部分，
因为我们现在（由于该定理）知道其中的所有项都> 5
还要注意，如果我们有一个排序的序列，并且想要找到任何
一个满足不等式的元素，那么查看末尾的元素就足够了。
本文收集自互联网，转载请注明来源。
如有侵权，请联系 [email protected] 删除。
我来说两句