如何更好地理解每比較一次比較二進制搜索？

Question

單比較每迭代二進制搜索的要點是什麼？你能解釋它是如何工作的嗎？

Answer 1

二元搜索有兩個原因，每次迭代一次比較。性能不太重要的是 。提前檢測完全匹配，每次迭代使用兩個 比較節省循環的平均一次迭代，而 （假設比較涉及重要工作），每次迭代比較一次 ，幾乎減半了每次迭代完成的工作。

二進制搜索一個整數數組，它可能無論如何沒有什麼區別 。即使是相當昂貴的比較，漸近地表現也是一樣的，在大多數情況下，可能不會有價值追求的是一半而不是一個負值。此外，昂貴的比較常常被編碼爲返回負數，零或正的<,==或>的函數，因此無論如何你都可以得到兩者的比較。

每次迭代比較一次進行二分搜索的重要原因是 ，因爲您可以獲得比僅僅一些等號匹配更有用的結果。主要 搜索你可以做的是...

• 一鍵>目標
• 一鍵> =目標
• 一鍵==目標
• 最後關鍵<目標
• 最後關鍵< =目標
• 最後一個關鍵==目標

這些都減少到相同的基本算法。理解這個足夠好的 ，你可以很容易地編寫所有的變體並不困難，但我沒有真正看到一個很好的解釋 - 只有僞代碼和數學證明。這是我試圖解釋的 。

有一些遊戲的想法是儘可能接近目標 沒有超調。將其改爲「下衝」，這就是「Find First>」所做的。考慮搜索過程中某個階段的範圍...

| lower bound  | goal     | upper bound 
+-----------------+-------------------------+-------------- 
|   Illegal | better   worse | 
+-----------------+-------------------------+-------------- 

仍然需要搜索當前上限和下限之間的範圍。 我們的目標是（通常）在某處，但我們還不知道在哪裏。 關於上限以上項目的一個有趣的觀點是，他們在 合法的意義上說他們比目標更重要。我們可以說，當前上限以上的項目 是我們迄今爲止最好的解決方案。我們甚至可以在一開始就說這個 ，儘管在那個位置可能沒有物品 - 從 的意義上說，如果沒有有效的範圍內解決方案，那麼不是 的最佳解決方案就是過去的上限。

在每次迭代時，我們選擇一個項目來比較上下限。 對於二分查找，這是一個舍入的中途項目。對於二叉樹搜索，它是由樹的結構決定的 。原理是一樣的。

由於我們正在搜索的項目大於我們的目標，我們使用Item [testpos] > goal比較測試項目 。如果結果是錯誤的，我們會超出（或低於 ）我們的目標，所以我們保留現有的最佳解決方案，並調整我們的下限。如果結果是真的，我們已經找到了一個新的最好的解決方案，所以我們調整上限以反映這一點。無論採用哪種方式，我們都不希望再次比較該測試項目，因此我們調整我們的 範圍以消除（僅僅是）從測試項目中搜索的範圍。因爲這個不小心，通常會導致無限循環。

通常，使用半開範圍 - 包含下限和獨佔上限。使用此係統，上限索引處的項目不在 搜索範圍內（至少不是現在），但它是是最好的解決方案。 移動下限時，將其移動到testpos+1（以排除您僅從 測試的項目）。當你移動上限時，你將它移動到 testpos（無論如何，上限是獨佔的）。

if (item[testpos] > goal) 
{ 
    // new best-so-far 
    upperbound = testpos; 
} 
else 
{ 
    lowerbound = testpos + 1; 
} 

在上限和下限之間的範圍內是空的（採用半開， 當兩個具有相同指數），你的結果是你最近最迄今爲止在 液，只需在你上面的上限（即在半開放的 的上限索引處）。

，所以該完整的算法是...

while (upperbound > lowerbound) 
{ 
    testpos = lowerbound + ((upperbound-lowerbound)/2); 

    if (item[testpos] > goal) 
    { 
    // new best-so-far 
    upperbound = testpos; 
    } 
    else 
    { 
    lowerbound = testpos + 1; 
    } 
} 

若要更改first key > goal到first key >= goal，你從字面上切換 比較運營商在if線。 相對運算符和目標可以由單個參數替代 - 一個謂詞函數，如果（且僅當）其參數位於目標的大於一側時返回true。

這給你「第一>」和「第一> =」。要獲得「first ==」，請使用「first> =」，並在循環退出後添加相等性檢查。

對於「last <」等，其原理與上述相同，但範圍爲 反映。這只是意味着你調整了邊界調整（但不包括 評論）以及更改運算符。但在此之前，請考慮以下內容...

a > b == !(a <= b) 
a >= b == !(a < b) 

另外...

• 位置（最後的鍵<目標）=位置（第一密鑰> =目標） - 1個
• 位置（最後的鍵< =目標）=位置（第一密鑰>目標） - 1

當我們在搜索過程中移動我們的界限時，雙方都會朝目標移動，直到他們相遇。還有剛剛低於下限特殊的項目，就像有隻超過上限時...

while (upperbound > lowerbound) 
{ 
    testpos = lowerbound + ((upperbound-lowerbound)/2); 

    if (item[testpos] > goal) 
    { 
    // new best-so-far for first key > goal at [upperbound] 
    upperbound = testpos; 
    } 
    else 
    { 
    // new best-so-far for last key <= goal at [lowerbound - 1] 
    lowerbound = testpos + 1; 
    } 
} 

因此，在某種程度上，我們同時運行兩個互補的搜索。當上限和下限相遇時，我們在該單一邊界的每一邊都有一個有用的搜索結果。

對於所有情況，原始「想象」出界 最佳到此位置是您的最終結果（在搜索範圍內沒有匹配）。在做最後的==檢查 第一個==和最後一個==情況之前，需要檢查它。這也可能是有用的行爲 - 例如如果 您正在尋找插入目標項目的位置，則在現有項目的 末尾添加該位置是正確的，如果所有現有項目 都小於您的目標項目。

一對夫婦對testpos的選擇筆記...

testpos = lowerbound + ((upperbound-lowerbound)/2); 

首先，這將不會溢出，不像比較明顯((lowerbound + upperbound)/2)。它也適用於指針以及整數 索引。

其次，該部門被假定爲圓形。下降非負數 是確定的（所有你可以肯定在C），因爲差異始終是非負數 無論如何。

這是一個方面，如果您使用非半開放式 範圍，可能需要謹慎，但是 - 確保測試位置在搜索範圍內，而不僅僅是在外面（在已經找到的最佳範圍之一上）目前爲止的職位）。

最後，在二叉樹搜索範圍的移動是隱性和 選擇testpos內置於樹的結構（可能是 不平衡），但同樣的原則也適用於搜索是什麼這樣做。在這個 的情況下，我們選擇我們的子節點縮小隱式範圍。對於第一場比賽 的情況，要麼我們找到了一個新的較小的最佳匹配（找到較小的孩子，希望找到一個更小，更好的孩子），或者我們已經超過（希望恢復的更高的孩子）。再次，可以通過切換比較運算符來處理四種主要情況。

順便說一句 - 有更多可能的操作符用於該模板參數。考慮按年份和月份排序的數組。也許你想找到特定年份的第一個項目。要做到這一點，編寫一個比較年份並忽略月份的比較函數 - 如果年份相同，則目標相當於平等，但目標值可能與密鑰的類型不同，該密鑰甚至沒有月份值比較。我認爲這是一個「部分關鍵比較」，並將其插入到二進制搜索模板中，並獲得我認爲的「部分關鍵搜索」。

編輯以下段落用於說「1999年12月31日等於2000年2月1日」。除非整個範圍也被認爲是平等的，否則這是行不通的。重點是開始和結束日期日期的所有三個部分都不相同，因此您不需要處理「部分」鍵，但被認爲等同於搜索的鍵必須在容器中形成一個連續的塊，這通常意味着在可能的鍵的有序集合中連續的塊。

它不完全是「部分」鍵。您的自定義比較可能會考慮到1999年12月31日等於2000年1月1日，但所有其他日期不同。關鍵在於自定義比較必須與排序的原始關鍵字一致，但考慮到所有不同的值可能不會太挑剔 - 它可以將一系列關鍵字視爲「等價類」。

---

關於我真的應該包括前界一個額外的音符，但也許我還沒有想過這個問題在當時這種方式。

思考邊界的一種方法是它們根本不是項目。一個綁定的兩個項目之間的邊界線，所以你可以很容易地爲編號的邊界線，你可以編號的項目...

|  |  |  |  |  |  |  |  | 
| +-+ | +-+ | +-+ | +-+ | +-+ | +-+ | +-+ | +-+ | 
| |0| | |1| | |2| | |3| | |4| | |5| | |6| | |7| | 
| +-+ | +-+ | +-+ | +-+ | +-+ | +-+ | +-+ | +-+ | 
|  |  |  |  |  |  |  |  | 
0  1  2  3  4  5  6  7  8 

明顯界限的編號與項目的編號。只要你從左到右編號，並用相同的方式爲你的項目編號（在這種情況下從零開始），結果與常見的半開公約相同。

將有可能選擇一箇中間範圍將範圍精確地平分爲兩個，但這不是二進制搜索的功能。對於二進制搜索，您可以選擇一個要測試的項目 - 不是綁定。該項目將在此迭代中進行測試，不得再次測試，因此它將從兩個子範圍中排除。

|  |  |  |  |  |  |  |  | 
| +-+ | +-+ | +-+ | +-+ | +-+ | +-+ | +-+ | +-+ | 
| |0| | |1| | |2| | |3| | |4| | |5| | |6| | |7| | 
| +-+ | +-+ | +-+ | +-+ | +-+ | +-+ | +-+ | +-+ | 
|  |  |  |  |  |  |  |  | 
0  1  2  3  4  5  6  7  8 
         ^
     |<-------------------|------------->| 
          | 
     |<--------------->| | |<--------->| 
      low range  i  hi range 

所以在算法testpos和testpos+1是翻譯項目索引，約束指數的兩種情況。當然，如果兩個邊界相等，則該範圍內沒有項目可供選擇，因此循環無法繼續，唯一可能的結果就是該邊界值。

上面顯示的範圍只是仍然需要搜索的範圍 - 我們打算在久經考驗的和已證明的更高範圍之間關閉的差距。

在此模型中，二分查找搜索兩個有序種類值之間的邊界 - 分類爲「較低」和歸類爲「較高」的那些邊界。謂詞測試將一個項目分類。沒有「平等」等級 - 等於鍵值是較高等級（對於x[i] >= key）或較低等級（對於x[i] > key）的一部分。