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:

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

迭代2:

  • i0j4
  • 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 })

更多教程: