動かしてわかる探索アルゴリズム入門｜線形探索と二分探索を体験しよう

アルゴリズムを学ぶときは、言葉だけで理解しようとするよりも、値を変えて動きを追うほうがつかみやすくなります。この記事では、データの中から目的の値を探す「探索アルゴリズム」を題材に、線形探索と二分探索の違いを動かしながら確認します。

どちらも「探す」という目的は同じですが、調べる順番や必要な前提が違います。線形探索は先頭から順番に確認する方法、二分探索は整列済みのデータを半分ずつ絞り込む方法です。

探索アルゴリズムとは

探索アルゴリズムとは、複数のデータの中から目的の値を見つけるための手順です。たとえば、名簿から名前を探す、商品一覧から価格を探す、ログの中からエラーを探すといった作業は、すべて探索として考えることができます。

プログラムでは、同じ結果を得られるとしても、手順によってかかる時間が変わります。データが少ないと差は小さく見えますが、件数が増えると「どの順番で調べるか」が重要になります。

動かしてわかる探索アルゴリズム

下の画面では、線形探索と二分探索を切り替えて実行できます。データや探す値を変え、結果を予想してから「1ステップ進める」または「最後まで実行」を押してください。現在位置、現在の値、比較回数、探索範囲が変わる様子を確認できます。

線形探索の考え方

線形探索は、データを先頭から順番に確認していく方法です。データが並び替えられていなくても使えるため、考え方はシンプルです。一方で、目的の値が最後のほうにある場合や、存在しない場合は、すべての値を確認する必要があります。

線形探索は、データの件数が少ないとき、並び順が決まっていないとき、または一度だけ軽く探せればよいときに向いています。たとえば、入力された数件の候補から一致するものを探す場合や、ログを上から順に見て最初のエラーを探す場合は、線形探索の考え方で十分なことがあります。

たとえば 3, 8, 12, 18, 25, 31, 42 の中から 25 を探す場合、3、8、12、18、25 の順に比較し、5回目の比較で見つかります。

JavaScriptの例

function linearSearch(list, target) {
  for (let i = 0; i < list.length; i++) {
    if (list[i] === target) {
      return i;
    }
  }
  return -1;
}

Pythonの例

def linear_search(values, target):
    for i, value in enumerate(values):
        if value == target:
            return i
    return -1

二分探索の考え方

二分探索は、整列済みのデータを対象に、中央の値を見ながら探索範囲を半分ずつ狭める方法です。中央の値が探す値より小さければ右側を探し、中央の値が大きければ左側を探します。

この方法は、データが小さい順や大きい順に並んでいることが前提です。並んでいないデータにそのまま使うと、正しく探せない可能性があります。前提が必要な代わりに、データ件数が増えたときの比較回数を大きく減らせます。

二分探索は、辞書や索引のように、すでに順番に並んでいるデータから探すときに向いています。商品ID、会員番号、日付順のデータなど、並び順を保てるデータでは強力です。一方で、データを探すたびに並べ替えが必要になる場合は、並べ替えの手間も含めて考える必要があります。

二分探索ではどうやって真ん中を決めるのか

二分探索では、現在の探索範囲の左端を left、右端を right として、中央の位置を (left + right) ÷ 2 で求めます。割り切れない場合は、小数点以下を切り捨てて整数の位置にします。

たとえば、位置0から6までの7個のデータなら、中央は (0 + 6) ÷ 2 = 3 です。位置0から2までに範囲が狭まったら、中央は (0 + 2) ÷ 2 = 1 になります。このように、毎回「今残っている範囲の真ん中」を見ます。

データの個数が奇数なら、真ん中の位置は1つに決まります。たとえば7個なら、0、1、2、3、4、5、6のうち、中央は位置3です。

では、データの個数が偶数の場合はどうでしょうか。たとえば位置0から5までの6個なら、計算は (0 + 5) ÷ 2 = 2.5 になります。配列の位置に2.5番目はないため、プログラムでは小数点以下を切り捨てて位置2を中央として扱うことが一般的です。

ここで大切なのは、「完全な中央を1つ選ぶ」ことではなく、「探索範囲をおおよそ半分に分ける」ことです。位置2を選んでも位置3を選んでも、手順として一貫していれば探索は進みます。この記事のJavaScriptとPythonの例では、小数点以下を切り捨てる方法で中央を決めています。

JavaScriptの例

function binarySearch(list, target) {
  let left = 0;
  let right = list.length - 1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);

    if (list[mid] === target) {
      return mid;
    }
    if (list[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  return -1;
}

Pythonの例

def binary_search(values, target):
    left = 0
    right = len(values) - 1

    while left <= right:
        mid = (left + right) // 2

        if values[mid] == target:
            return mid
        if values[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1

比較回数を見ると違いがわかる

線形探索は、最悪の場合すべての値を確認します。二分探索は、1回比較するたびに候補をおおよそ半分に減らします。そのため、データが多いほど二分探索の強みが出ます。

ただし、二分探索はいつでも使えるわけではありません。データが整列されているか、整列にかかる手間を含めても有利か、途中でデータが頻繁に追加・変更されるかといった条件を考える必要があります。

まとめ

探索アルゴリズムは、「どの順番で調べるか」を手順として整理する考え方です。線形探索は単純で使いやすく、二分探索は整列済みデータに対して効率よく探せます。

アルゴリズムを理解するときは、コードだけでなく、現在位置、比較回数、条件分岐、繰り返しの流れを見ることが重要です。値を変えて実行し、どのタイミングで探索範囲が変わるのかを確認すると、処理の意味をより具体的に理解できます。