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

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

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

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

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

実際の開発現場では、標準ライブラリにも似た機能があり、大量のデータの中から特定の値を高速に探したい場面で、二分探索の考え方が広く応用されています。

📖 お手本コード

fun binarySearch(arr: List<Int>, target: Int): Int {
    var low = 0
    var high = arr.size - 1
    while (low <= high) {
        val mid = (low + high) / 2
        when {
            arr[mid] == target -> return mid
            arr[mid] < target -> low = mid + 1
            else -> high = mid - 1
        }
    }
    return -1
}

fun main() {
    val nums = listOf(1, 3, 5, 7, 9, 11)
    println(binarySearch(nums, 7))
    println(binarySearch(nums, 4))
}

✍️ あなたのコード

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

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

🎯

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