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">>=</span> <span style="color:#a6e22e">x</span> })
<span style="color:#66d9ef">if</span> <span style="color:#a6e22e">i</span> < len(<span style="color:#a6e22e">a</span>) <span style="color:#f92672">&&</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 })
その他のチュートリアル:
- NGINXリバースプロキシを使用してGoサービスを提供する
- Goで構造体のコピーを作成する
- GoWebサーバーの基本
- Goでのマップタイプの並べ替え
- 一言で言えばポインタを移動します
- タグの説明に行く
- 日付と時刻のフォーマットに移動
- Goを使用したJSON処理
- 可変個引数関数に移動
- GoStringsチートシート
- GoEmptyインターフェイスの説明
- Go withVSCodeとDelveのデバッグ
- NamedGoはパラメータを返します
- Goで乱数と文字列を生成する
- Goプロジェクトのファイルシステム構造
- Goに実装された二分探索アルゴリズム
- Goでのコマンドラインフラグの使用
- GOPATHの説明
- Goでコマンドラインアプリを作成する:lolcat
- Goを使用したCLIコマンドの作成:cowsay
- Goでのシェルパイプの使用
- CLIチュートリアルに移動:フォーチュンクローン
- Goを使用してフォルダ内のファイルを一覧表示します
- Goを使用して、GitHubからリポジトリのリストを取得します
- 移動し、文字列のスライスをファイルに追加します
- 文字列をバイトスライスに変換します
- GoでローカルGitの貢献を視覚化する
- GoCPUとメモリプロファイリングの開始
- Goプログラムの「インデックス作成をサポートしていません」エラーを解決する
- Goプログラムでの実行時間の測定
- 重複するタイトルを検出するためにGoを使用してWebクローラーを構築する
- ベストプラクティスに進む:ポインターまたは値のレシーバー?
- ベストプラクティスに進む:メソッドまたは関数を使用する必要がありますか?
- データ構造の移動:設定
- マップのチートシートに移動
- Goでジェネリック型の実装を生成する
- Goデータ構造:辞書
- Goデータ構造:ハッシュテーブル
- Go throughChannelsにイベントリスナーを実装する
- Goデータ構造:スタック
- データ構造の移動:キュー
- Goデータ構造:二分探索木
- Goデータ構造:グラフ
- Goデータ構造:リンクリスト
- Goデータ構造の完全ガイド
- Go値の比較
- Goはオブジェクト指向ですか?
- GoでのSQLデータベースの操作
- Goでの環境変数の使用
- チュートリアルに進む:PostgreSQLに裏打ちされたREST API
- GoWebサーバーでのCORSの有効化
- DockerコンテナへのGoアプリケーションのデプロイ
- GoがPHP開発者として学ぶための強力な言語である理由
- 移動し、io.Reader.ReadString改行文字を削除します
- 移動、変更を監視してプログラムを再構築する方法
- 行って、日付からの月を数えます
- GoでHTTPPOSTパラメーターにアクセスする