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

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

二分探索は、並び替え済みの配列に対して、探す範囲を毎回半分に絞り込んでいく探索方法です。1つずつ順番に調べる線形探索よりもずっと少ない回数で目的の値にたどり着けます。

サンプルコードでは、lowとhighという2つの位置から範囲の中央midを計算し、目的の値と比較しながらlowかhighを更新して範囲を絞り込んでいます。\は整数同士の割り算で小数点以下を切り捨てる演算子です。

初心者がよくつまずくのが、二分探索を使うには配列が事前に並び替えられている必要がある点です。並び替えられていない配列に対して二分探索を行っても、正しい結果が得られない場合があります。

実際の開発現場では、大量のデータの中から特定の値を高速に探したい場面(辞書検索やデータベースの索引など)で、二分探索の考え方が広く応用されています。

📖 お手本コード

Function BinarySearch(arr() As Integer, target As Integer) As Integer
    Dim low As Integer = 0
    Dim high As Integer = arr.Length - 1
    While low <= high
        Dim mid As Integer = (low + high) \ 2
        If arr(mid) = target Then
            Return mid
        ElseIf arr(mid) < target Then
            low = mid + 1
        Else
            high = mid - 1
        End If
    End While
    Return -1
End Function

Dim nums() As Integer = {1, 3, 5, 7, 9, 11}
Console.WriteLine(BinarySearch(nums, 7))
Console.WriteLine(BinarySearch(nums, 4))

✍️ あなたのコード

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

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

🎯

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