二進位制搜尋

介紹

二進位制搜尋是一種分而治之搜尋演算法。它使用 O(log n) 時間來查詢搜尋空間中元素的位置，其中 n 是搜尋空間的大小。

二進位制搜尋的工作原理是在將目標值與搜尋空間的中間值進行比較後，在每次迭代時將搜尋空間減半。

要使用二進位制搜尋，必須以某種方式對搜尋空間進行排序（排序）。儘管它們不違反二進位制搜尋屬性，但無法區分重複條目（根據比較函式進行比較的條目）。

通常，我們使用小於（<）作為比較函式。如果 a <b，它將返回 true。如果 a 不小於 b 且 b 不小於 a，則 a 和 b 相等。

示例問題

你是一名經濟學家，但是非常糟糕。你的任務是找到大米的均衡價格（即供給=需求的價格）。

請記住，設定的價格越高，供應量越大，需求量越小

由於你的公司在計算市場力量方面非常有效，因此當大米的價格設定為特定價格時，你可以立即獲得以米為單位的供需情況。

你的老闆儘快得到均衡價格，但告訴你均衡價格可以是一個至多為 4 的正整數，並且保證在該範圍內恰好是 1 個正整數解。所以在你失去它之前就開始工作吧！

你可以呼叫函式 getSupply(k) 和 getDemand(k)，它們將完全按照問題中的說明進行操作。

示例說明

我們的搜尋空間是從 1 到 10^17。因此，線性搜尋是不可行的。

然而，請注意，隨著 k 的上升，getSupply(k) 增加而 getDemand(k) 減少。因此，對於任何 x > y，getSupply(x) - getDemand(x)>getSupply(y) - getDemand(y)。因此，此搜尋空間是單調的，我們可以使用二進位制搜尋。

以下 psuedocode 演示了二進位制搜尋的用法：

high = 100000000000000000     <- Upper bound of search space
low = 1                       <- Lower bound of search space
while high - low > 1
    mid = (high + low) / 2    <- Take the middle value
    supply = getSupply(mid)  
    demand = getDemand(mid)
    if supply > demand        
        high = mid             <- Solution is in lower half of search space
    else if demand > supply
        low = mid              <- Solution is in upper half of search space
    else                       <- supply==demand condition
        return mid             <- Found solution

該演算法在 14 時執行。這可以推廣到~O(log S) 時間，其中 S 是搜尋空間的大小，因為在 while 迴圈的每次迭代中，我們將搜尋空間減半（ 從[low：high]到[low：mid]或[mid：high] ）。

用遞迴實現二進位制搜尋

int binsearch(int a[], int x, int low, int high) {
    int mid;

    if (low > high)
      return -1;

    mid = (low + high) / 2;

    if (x == a[mid]) {
        return (mid);
    } else 
    if (x < a[mid]) {
        binsearch(a, x, low, mid - 1);
    } else {
        binsearch(a, x, mid + 1, high);
    }
}