Go中的二進制搜索算法

如何在Go中實現二進制搜索算法

二元搜尋是一種簡單的算法，可以在排序數組，並且通常被稱為學習新的編程語言時要學習的代碼示例。

功效

這非常有效：

時間：O（log n），這是最差的對數
空間：0(1)，需要持續的時間

理論

給定一個已排序的數組，我們在中間選擇項Y，然後將其與目標值X進行比較。

如果Y與X匹配，則返回Y位置，然後退出。

我們確定是否X <Y，在這種情況下，我們丟棄右側，然後移至左側的中間，並重複與上述相同的操作。

當Y最終與X匹配時，搜索結束。如果這沒有發生，我們將返回X在數組中所處的位置。

執行

幸運的是，Go標準庫在其標準庫中提供了一個二叉樹實現sort包裝，在sort.Search()。

讓我們來看看API的用法（如包裝文檔中所述），因此我們知道sort.Search應該返回：

package main
import (
“fmt”
“sort”
)
func main() {
a := []int{1, 3, 6, 10, 15, 21, 28, 36, 45, 55}
x := 6
<span style="color:#a6e22e">i</span> <span style="color:#f92672">:=</span> <span style="color:#a6e22e">sort</span>.<span style="color:#a6e22e">Search</span>(len(<span style="color:#a6e22e">a</span>), <span style="color:#66d9ef">func</span>(<span style="color:#a6e22e">i</span> <span style="color:#66d9ef">int</span>) <span style="color:#66d9ef">bool</span> { <span style="color:#66d9ef">return</span> <span style="color:#a6e22e">a</span>[<span style="color:#a6e22e">i</span>] <span style="color:#f92672">&gt;=</span> <span style="color:#a6e22e">x</span> })
<span style="color:#66d9ef">if</span> <span style="color:#a6e22e">i</span> &lt; len(<span style="color:#a6e22e">a</span>) <span style="color:#f92672">&amp;&amp;</span> <span style="color:#a6e22e">a</span>[<span style="color:#a6e22e">i</span>] <span style="color:#f92672">==</span> <span style="color:#a6e22e">x</span> {
    <span style="color:#a6e22e">fmt</span>.<span style="color:#a6e22e">Printf</span>(<span style="color:#e6db74">"found %d at index %d in %v\n"</span>, <span style="color:#a6e22e">x</span>, <span style="color:#a6e22e">i</span>, <span style="color:#a6e22e">a</span>)
} <span style="color:#66d9ef">else</span> {
    <span style="color:#a6e22e">fmt</span>.<span style="color:#a6e22e">Printf</span>(<span style="color:#e6db74">"%d not found in %v\n"</span>, <span style="color:#a6e22e">x</span>, <span style="color:#a6e22e">a</span>)
}
}

sort.Search返回索引i，而我們只需要確保該索引實際上包含x。

當然，我們想知道它是如何在內部實現的。由於標準庫是用Go語言和開源語言編寫的，因此很容易看到sort.Search實現：

func Search(n int, f func(int) bool) int {
    // Define f(-1) == false and f(n) == true.
    // Invariant: f(i-1) == false, f(j) == true.
    i, j := 0, n
    for i < j {
        h := i + (j-i)/2 // avoid overflow when computing h
        // i ≤ h < j
        if !f(h) {
            i = h + 1 // preserves f(i-1) == false
        } else {
            j = h // preserves f(j) == true
        }
    }
    // i == j, f(i-1) == false, and f(j) (= f(i)) == true  =>  answer is i.
    return i
}

讓我們分解一下：

給定一個具有長度的數組n，以及比較功能f（內部評估x >= a[h]），我們開始迭代數組a。

讓我們使用示例中使用的實際值，可以更輕鬆地顯示正在發生的事情。

數據：

a := []int{1, 3, 6, 10, 15, 21, 28, 36, 45, 55}
x := 6

迭代1：

i是0，j是9。
h計算為(0 + (9-0) / 2)=4
a[h]是15。這意味著我們執行j = h

迭代2：

i是0，j是4。
h計算為(0 + (4-0) / 2)=2
a[h]是6。我們找到了x，這意味著我們返回h = 2

搜索逆序

由於我們可以將函數傳遞給sort.Search，很容易搜索以相反順序排序的數組，例如

a := []int{55, 45, 36, 28, 21, 15, 10, 6, 3, 1}
x := 6

通過傳遞一個比較的函數a[i] <= x代替a[i] >= x。

i := sort.Search(len(a), func(i int) bool { return a[i] <= x })

Go中的二進制搜索算法

如何在Go中實現二進制搜索算法

功效

理論

執行

搜索逆序

更多教程：