binary-search - 离散二分搜索主要理论

Question

我读过这个：https ://www.topcoder.com/community/competitive-programming/tutorials/binary-search 。有些部分看不懂==>

我们可以称之为主定理的内容是，当且仅当对于 S 中的所有 x，p(x) 意味着所有 y > x 的 p(y) 时，才可以使用二分搜索。这个属性是我们在丢弃搜索空间的后半部分时使用的。相当于说 ¬p(x) 意味着所有 y < 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) 是真的，但不是。

那么问题是什么？

标签： binary-search

Answer 1

我们可以在寻找精确值时使用该定理，因为我们
只在丢弃一半时使用它。如果我们正在寻找说 5，
并且我们在中间找到说 6，我们可以丢弃上半部分，
因为我们现在知道（由于定理）那里的所有项目都 > 5

还要注意，如果我们有一个排序序列，并且想要找到任何
满足不等式的元素，那么查看末尾元素就足够了。