Topcoder二進制搜索教程

Question

我們可以稱爲主要定理說明：當且僅當對於S中的所有x，p（x）意味着所有y> x的p（y）。當我們丟棄搜索空間的後半部分時，這個屬性就是我們所使用的。這相當於說，對於所有的y，p（x）暗示p（y）x（符號¬表示邏輯非運算符），這是我們在丟棄前半部分搜索空間時所使用的。

請用簡單和詳細的術語解釋本段。

Answer 1

請考慮p(x)是x的一些財產。當使用二進制搜索時，此屬性通常爲x，它們比您要查找的其他值k更大，更小或相等。

我們可以稱爲主要定理說明：當且僅當對於S中的所有x，p（x）意味着所有y> x的p（y）。

讓我們說x是列表中的一些中間值，您正在尋找地方k是。我們也可以說p(x)意味着k大於x。如果列表按升序排序，則x（y > x）右側的所有值y也必須大於k（該房產爲transitive），因此p(y)也適用於所有y。這是二進制搜索的基礎。如果您正在尋找k，並且已知某些值x大於k，則比其右側的所有元素都大於k。請注意，如果列表已排序，則這僅爲真。考慮您正在查找的列表[a,b,c]和值k。如果知道a < b和b < c，如果k < b爲真，那麼k < c也必須爲真。

這個屬性是我們在丟棄後半部分搜索空間時使用的。

這是以前的結論允許你做的。如您所知，x的財產也同樣適用於所有y（也就是說，它們是而不是因爲它們更大，所以您要查找的元素）比放棄它們更安全，因此您一直在尋找k只在下半部分。

該段的其餘部分對於丟棄下半部分說幾乎相同的東西。

簡而言之，p(x)是一些傳遞屬性，它應該適用於任何給定值x（同樣，因爲它是可傳遞的）右側的所有值。另一方面，¬p(x)應該保留x左側的所有值。通過能夠得出結論，那些不是你正在尋找的元素，你可以得出結論，放棄列表的一半是安全的。