7.探索アルゴリズム

学習目標

• 「配列からある値を探す」問題に対して、線形探索を自力で書ける
• 二分探索の仕組みを理解し、トレースできる
• 線形探索と二分探索の探索回数の違いを説明できる

---

1. 探索

「100人分のテストの点数が入った配列から、90点の人が何番目にいるかを調べたい」——このように、データの中から目的の値を見つける処理を 探索（サーチ）と呼びます。

探索はプログラミングで最も基本的なアルゴリズムの1つです。代表的な探索アルゴリズムに線形探索と二分探索があります。

2. 線形探索

2-1. 考え方

線形探索 は、最もシンプルな探索方法です。配列の先頭から順に1つずつ調べて、目的の値が見つかったらその位置を返します。

たとえば、以下の配列から 88 を探す場合、先頭の 34 から順に比較していき、4番目（インデックス 3）で一致します。

┌──┬──┬──┬──┬──┐
│３４│７２│１５│８８│４３│
└──┴──┴──┴──┴──┘

配列に存在しない値を探す場合は、全要素を調べて「見つからなかった」と判定します。

2-2. 実装の方針

図で確認した手順をプログラムにするために、1つずつ考えていきます。

1. 先頭から1つずつ調べる

   for ループで配列の要素にインデックス 0 から末尾まで順にアクセスすることで表現できます。

   対応するコード

   for (let i = 0; i < arr.length; i++) {

2. 目的の値と比較する

   各要素を調べるたびに、arr[i] === target で比較します。一致したら、その時点のインデックス i を return で返します。return が実行されるとループも関数も終了するので、残りの要素は調べません。

   対応するコード

   if (arr[i] === target) {
     return i;
   }

3. 見つからなければ -1 を返す

   ループが最後まで回っても一致する要素がなかった場合は、ループの後で return -1 を返します。

   対応するコード

   return -1;

Info

-1 は「見つからなかった」ことを表す慣習的な値です。インデックスは 0 以上の整数なので、-1 が返ってきたら「該当なし」と判断できます。

2-3. 実装

関数版

search.js

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

const data = [34, 72, 15, 88, 43];

console.log(linearSearch(data, 88));
console.log(linearSearch(data, 43));
console.log(linearSearch(data, 99));

3
4
-1

関数を使わない版

search.js

const data = [34, 72, 15, 88, 43];
const target = 88;
let result = -1; // 見つからなかったら -1 のまま

for (let i = 0; i < data.length; i++) {
  if (data[i] === target) {
    result = i;
    break; // 見つかったのでループを抜ける
  }
}

console.log(result);

3

Info

関数を使わない版では、値が見つかった時点でループを抜けるために break を使います。break はループの途中で繰り返しを終了する命令です。

linearSearch(data, 88) をトレースします。

i	arr[i]	arr[i] === target	操作
0	34	false	—
1	72	false	—
2	15	false	—
3	88	true	return 3

i = 3 で一致したので、ループの残り（i = 4）には到達しません。

2-4. 条件を変えた探索

線形探索は「一致する値を探す」だけでなく、条件を変えてさまざまな探索に応用できます。たとえば、最初の偶数を探す関数は次のように書けます。

search.js

function findFirstEven(arr) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] % 2 === 0) {
      return i;
    }
  }
  return -1;
}

console.log(findFirstEven([7, 3, 8, 1, 4]));
console.log(findFirstEven([1, 3, 5]));

2
-1

構造は linearSearch と同じです。arr[i] === target の部分が arr[i] % 2 === 0 に変わっただけです。「先頭から順に調べて、条件を満たす要素が見つかったらそのインデックスを返す」というパターンは共通しています。

2-5. 探索回数

線形探索は先頭から1つずつ調べるので、最悪の場合（目的の値が末尾にある、または存在しない）は配列の全要素を調べます。

要素数が 10 なら最大 10 回、要素数が 1000 なら最大 1000 回です。要素数に比例して探索回数が増えます。

3. 二分探索

3-1. 線形探索の限界

要素数が 100 万の配列から値を探すとします。線形探索では最悪 100 万回の比較が必要で、データが大きくなるほど時間がかかります。

ただし、配列がソート（昇順に並べ替え）済みであれば、もっと少ない回数で探す方法があります。

3-2. 考え方

「1 から 100 の中で正解の数を当てるゲーム」を考えます。答えるたびに「もっと大きい / 小さい / 正解」と教えてもらえます。

最初は真ん中の 50 を答えるのが最も効率的です。違ったら次の範囲（1〜49 か 51〜100）の真ん中をまた答えます。このように「探す範囲を半分に絞る」ことを繰り返せば、100 個の数でも最大 7 回で正解にたどり着けます。

ソート済みの配列に対して同じ考え方を使うのが 二分探索 です。配列から 30 を探す例で見てみます。

┌──┬──┬──┬──┬──┬──┬──┬──┬──┐
│１０│２０│３０│４０│５０│６０│７０│８０│９０│
└──┴──┴──┴──┴──┴──┴──┴──┴──┘

真ん中の要素と目的の値を比較して、目的の値がある側に範囲を絞ります。

1. 配列全体の真ん中は 50。30 < 50 なので左半分に範囲を絞る
2. 残った範囲の真ん中は 20。30 > 20 なので右半分に範囲を絞る
3. 残った範囲の真ん中は 30。一致したので位置 2 を返す

9 個の要素に対して、たった 3 回の比較で見つかりました。

Warning

二分探索は 配列がソート済みでなければ使えません。ソートされていない配列には線形探索を使います。

3-3. 実装の方針

二分探索の手順をプログラムにするために、何が必要かを1つずつ考えていきます。

1. 探索範囲を変数で管理する

   「今どこからどこまでを探しているか」を記録する必要があります。探索範囲の左端のインデックスを low、右端のインデックスを high とします。最初は配列全体が対象なので low = 0、high = 8（要素数 - 1）です。

   対応するコード

   let low = 0;
   let high = arr.length - 1;

2. 真ん中の位置を求める

   low と high の中間を Math.floor((low + high) / 2) で計算します。この値を mid とします。

   対応するコード

   const mid = Math.floor((low + high) / 2);

3. 真ん中の要素と比較して範囲を絞る

   arr[mid] と target を比較すると、3つの場合に分かれます。

   • 一致した → mid を返して終了
   • target のほうが大きい → 目的の値は右半分にある → low = mid + 1
   • target のほうが小さい → 目的の値は左半分にある → high = mid - 1

   mid + 1 や mid - 1 にするのは、mid の位置は既に調べたので、次の探索範囲に含める必要がないためです。

   対応するコード

   if (arr[mid] === target) {
     return mid;
   } else if (arr[mid] < target) {
     low = mid + 1;
   } else {
     high = mid - 1;
   }

4. ループの終了条件を決める

   範囲を絞り続けると、いずれ low が high を超えます。low > high になったら探索範囲が空になったことを意味するので、「見つからなかった」と判定します。

   対応するコード

   while (low <= high) {
     // (ステップ 2, 3 の処理)
   }
   return -1;

3-4. 実装

関数版

search.js

function binarySearch(arr, target) {
  let low = 0;
  let high = arr.length - 1;

  while (low <= high) {
    const mid = Math.floor((low + high) / 2);

    if (arr[mid] === target) {
      return mid;
    } else if (arr[mid] < target) {
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }

  return -1;
}

const data = [10, 20, 30, 40, 50, 60, 70, 80, 90];

console.log(binarySearch(data, 30));
console.log(binarySearch(data, 80));
console.log(binarySearch(data, 55));

2
7
-1

関数を使わない版

search.js

const data = [10, 20, 30, 40, 50, 60, 70, 80, 90];
const target = 30;
let low = 0; // 探索範囲の左端
let high = data.length - 1; // 探索範囲の右端
let result = -1;

while (low <= high) {
  const mid = Math.floor((low + high) / 2); // 範囲の真ん中

  if (data[mid] === target) {
    result = mid;
    break; // 見つかったのでループを抜ける
  } else if (data[mid] < target) {
    low = mid + 1; // 右半分に絞る
  } else {
    high = mid - 1; // 左半分に絞る
  }
}

console.log(result);

2

3-5. トレース

配列 [10, 20, 30, 40, 50, 60, 70, 80, 90] を使って、二分探索の動きをトレースします。

まず、値が見つかる場合として binarySearch(data, 80) を見てみます。

ステップ	low	high	mid	arr[mid]	比較	操作
1	0	8	4	50	80 > 50	low = 5
2	5	8	6	70	80 > 70	low = 7
3	7	8	7	80	80 === 80	return 7

3 回の比較で見つかりました。

次に、値が見つからない場合として binarySearch(data, 55) を見てみます。

ステップ	low	high	mid	arr[mid]	比較	操作
1	0	8	4	50	55 > 50	low = 5
2	5	8	6	70	55 < 70	high = 5
3	5	5	5	60	55 < 60	high = 4
4	5	4	—	—	low > high	return -1

4 回目はループに入る前に low > high になっているので、mid は計算されません（表の —）。探索範囲が空になり、「見つからなかった」と判定されます。

3-6. 探索回数の比較

線形探索は要素数に比例して探索回数が増えます。二分探索は毎回範囲を半分にするので、探索回数は大幅に少なくなります。

要素数	線形探索（最大）	二分探索（最大）
10	10 回	4 回
100	100 回	7 回
1,000	1,000 回	10 回
1,000,000	1,000,000 回	20 回

二分探索の最大探索回数は、要素数を何回 2 で割れるか（＝ 2 の何乗か）に対応します。1,000,000 は約 2^20 なので、最大 20 回です。

Tip

小さな配列や、一度だけ探すような場面では線形探索で十分です。要素数が多く、ソート済みで何度も探すなら二分探索を選びます。

4. 演習

演習: 探索アルゴリズム