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でバイナリ検索アルゴリズムを実装する方法

効率

理論

実装

逆順で検索

その他のチュートリアル：