我們如果在一個序列中搜尋一個元素的時候, 通常是從序列的頭部開始, 不斷地進行比較, 直到找到這個元素或著比較到尾部也無法找到這個元素. 這是針對不規則的序列來說的, 因為針對一個未知的序列, 搜尋一般沒有什麼規律可言, 而搜尋的時間也完全是 "看運氣". 但是如果給定的序列已經有序, 我們就可以改進這個從頭到尾搜尋的演算法, 實現出更高效的搜尋演算法

考慮一個有序的序列, 這個序列中的元素是從左至右逐漸增大的, 那麼從左到右搜尋相對來說是比較費時的. 如果我們直接把元素和中間元素比較, 如果元素比中間元素要小, 那麼就在中間元素的左側搜尋; 如果元素比中間元素大, 那麼就在中間元素的右側搜尋. 不斷重複上述步驟, 直到搜尋完畢, 我們會發現, 這種方式要優於從左至右逐個搜尋

在第一次搜尋中, 我們發現 mid 並不是我們要搜尋的元素, 而且我們要搜尋的元素比 mid 中的元素要大. 因此, 之後要在 mid 之後進行搜尋. 由於 mid 中的元素我們已經比較過了, 因此下一次搜尋的 begin 應該從 mid + 1 開始

mid 被指向新的值, 通過比較, 我們發現 mid 的值不是我們要搜尋的元素, 而且這次我們要搜尋的元素比 mid 中的元素小. 因此, 之後要在 mid 之前進行搜尋. 此時, 將 end 的值更新為 mid - 1

這一次, mid 的值和我們要搜尋的值相等, 因此 mid 的位置便是我們搜尋的值對應的位置

對比從左至右的順序搜尋, 二分搜尋只比較了 3 次, 而順序搜尋比較了 6 次. 當然, 並不是所有的二分搜尋都比順序搜尋要快. 比如, 當搜尋的元素位於序列前面的時候, 順序搜尋可能會比二分搜尋要快得多. 但是平均來說, 對於有序序列的搜尋, 二分搜尋要優於順序搜尋

假如搜尋不成功, 應該如何處理呢? 我們稍微增大要搜尋的值, 設定其為 17, 並且回到上一次搜尋的結果

由於 mid 中的值和要搜尋的值不相等, 並且比搜尋的值要大, 因此要在 mid 之前進行搜尋, 此時 end 被更新為 mid - 1

通過比較, mid 中的值比搜尋的值要小, 因此 mid 被更新為 begin + 1

此時, 我們發現 end < begin, 這本不應該發生! 因此, 可以將次作為搜尋無結果的標誌

int binary_search(const int arr[], int size, int value) {

    auto left {0}, right {size - 1};

    while(left <= right) {

        auto middle {(left + right) / 2};

        if(value == arr[middle]) {

            return middle;

        }else if(value < arr[middle]) {

            right = middle - 1;

        }else {

            left = middle - 1;

        }

    }

    return -1;

}

對於泛型的實作方式, 可以參考本人的 GitHub : GitHub 點擊直達