Topcoder 二进制搜索教程
Topcoder Binary search Tutorial
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.
请用更简单、更详细的术语解释这一段。
考虑 p(x) 是 x 的一部分 属性。使用二进制搜索时，此 属性 通常 x 大于、小于或等于您要查找的某个其他值 k。
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.
假设 x 是列表中间的某个值，您正在寻找 k 的位置。也可以说 p(x) 意味着 k 大于 x。如果列表按升序排序，则 x 右侧的所有值 y (y > x) 也必须大于 k（属性是 transitive)，因此 p(y) 也适用于所有 y。这是二分查找的基础。如果您正在寻找 k 并且已知某个值 x 大于 k，则其右侧的所有元素也都大于 k。请注意，这仅在列表已排序时才成立。考虑您要查找的列表 [a,b,c] 和一个值 k。如果已知 a < b 和 b < c，如果 k < b 为真，则 k < c 也必须为真。
This property is what we use when we discard the second half of the search space.
这是前面的结论允许你做的。如您所知，适用于 x 的 属性 也适用于所有 y（也就是说，它们 而不是 您要查找的元素，因为它们比丢弃它们要安全得多），因此您只在下半部分继续寻找 k。
该段的其余部分对于丢弃下半部分说的几乎相同。
简而言之，p(x) 是一些可传递的 属性，它应该持有任何给定值 x 右边的所有值（同样，因为它是可传递的）。另一方面，¬p(x) 应适用于 x 左侧的所有值。通过得出这些不是您要查找的元素的结论，您可以得出结论，丢弃列表的任何一半都是安全的。
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.
请用更简单、更详细的术语解释这一段。
考虑 p(x) 是 x 的一部分 属性。使用二进制搜索时，此 属性 通常 x 大于、小于或等于您要查找的某个其他值 k。
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.
假设 x 是列表中间的某个值，您正在寻找 k 的位置。也可以说 p(x) 意味着 k 大于 x。如果列表按升序排序，则 x 右侧的所有值 y (y > x) 也必须大于 k（属性是 transitive)，因此 p(y) 也适用于所有 y。这是二分查找的基础。如果您正在寻找 k 并且已知某个值 x 大于 k，则其右侧的所有元素也都大于 k。请注意，这仅在列表已排序时才成立。考虑您要查找的列表 [a,b,c] 和一个值 k。如果已知 a < b 和 b < c，如果 k < b 为真，则 k < c 也必须为真。
This property is what we use when we discard the second half of the search space.
这是前面的结论允许你做的。如您所知，适用于 x 的 属性 也适用于所有 y（也就是说，它们 而不是 您要查找的元素，因为它们比丢弃它们要安全得多），因此您只在下半部分继续寻找 k。
该段的其余部分对于丢弃下半部分说的几乎相同。
简而言之，p(x) 是一些可传递的 属性，它应该持有任何给定值 x 右边的所有值（同样，因为它是可传递的）。另一方面，¬p(x) 应适用于 x 左侧的所有值。通过得出这些不是您要查找的元素的结论，您可以得出结论，丢弃列表的任何一半都是安全的。