二分探索(バイナリサーチ)のアルゴリズム

このレッスンでは、Goで二分探索(バイナリサーチ)のアルゴリズムを実装する方法を学び、効率よく値を探す考え方を理解することを目標にします。「Go言語二分探索実装」で調べている方向けです。

二分探索は、並び替え済みのデータから目的の値を効率よく探すアルゴリズムです。「辞書を開くとき、真ん中あたりから探して範囲を半分に絞っていく」ようなイメージです。

サンプルコードでは、lowとhighという2つの位置から範囲の中央midを計算し、目的の値と比較しながらlowかhighを更新して範囲を絞り込んでいます。先頭から1つずつ調べる方法に比べて、データ量が多いほど圧倒的に速く目的の値を見つけられます。

初心者がよくつまずくのが、二分探索を使うには配列が事前に並び替えられている必要がある点です。探索対象のデータがすでに並び替えられていることが前提条件なので、事前のソートを忘れないようにしましょう。

実際の開発現場では、標準ライブラリにもsort.Searchという実装があり、大量のデータから高速に値を探したい場面で広く応用されています。

📖 お手本コード

package main

import "fmt"

func binarySearch(arr []int, target int) int {
    low, high := 0, len(arr)-1
    for low <= high {
        mid := (low + high) / 2
        if arr[mid] == target {
            return mid
        } else if arr[mid] < target {
            low = mid + 1
        } else {
            high = mid - 1
        }
    }
    return -1
}

func main() {
    nums := []int{1, 3, 5, 7, 9, 11}
    fmt.Println(binarySearch(nums, 7))
    fmt.Println(binarySearch(nums, 4))
}

✍️ あなたのコード

コードを書いたら「実行する」を押してください

🧪 このサイトではGoを直接コンパイル・実行できないため、お手本コードと同じ内容を入力できたかをその場で判定します(採点はブラウザ内だけで行われ、どこにも送信されません)。

🎯

ここまでできればゴール達成!
大量のデータの中から目的の値を高速に見つけ出せるようになります。