离散二分查找主要理论
Discrete Binary Search Main Theory
我已阅读：https://www.topcoder.com/community/competitive-programming/tutorials/binary-search。
有些地方我看不懂==>
What we can call the main theorem states that binary search can be
used if and only if for all x in S, p(x) implies p(y) for all y > x.
This property is what we use when we discard the second half of the
search space. It is equivalent to saying that ¬p(x) implies ¬p(y) for
all y < x (the symbol ¬ denotes the logical not operator), which is
what we use when we discard the first half of the search space.
但我认为当我们想在数组中找到一个元素（只检查是否相等）时这个条件不成立，这个条件只在我们试图找到不等式时成立，例如当我们正在搜索时大于或等于我们的目标值的元素。
示例：我们在此数组中找到 5。
indexes=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
还要注意，如果我们有一个排序序列，并且想要找到任何元素
满足不等式，看最后的元素就够了。
我已阅读：https://www.topcoder.com/community/competitive-programming/tutorials/binary-search。 有些地方我看不懂==>
What we can call the main theorem states that binary search can be used if and only if for all x in S, p(x) implies p(y) for all y > x. This property is what we use when we discard the second half of the search space. It is equivalent to saying that ¬p(x) implies ¬p(y) for all y < x (the symbol ¬ denotes the logical not operator), which is what we use when we discard the first half of the search space.
但我认为当我们想在数组中找到一个元素（只检查是否相等）时这个条件不成立，这个条件只在我们试图找到不等式时成立，例如当我们正在搜索时大于或等于我们的目标值的元素。
示例：我们在此数组中找到 5。
indexes=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
还要注意，如果我们有一个排序序列，并且想要找到任何元素
满足不等式，看最后的元素就够了。