探索・整列と処理量

指導者向けの公開補足

学習本文に加えて、指導の視点・背景・授業での確かめ方を示します。どなたでも読めます。

指導の焦点

二分探索は整列済みなどの前提があることを先に確認する。探索だけ速くても、整列の準備やデータ更新の費用がかかる。

一歩踏み込んだ背景

処理量の比較では、データ件数の増え方に対する比較回数を調べる。小さな入力で測定した一回の時間だけでは、一般的な優劣は言えない。

授業での確かめ方

線形探索と二分探索で、先頭・末尾・存在しない値を探す。整列の向きや重複値も確認し、返す結果の仕様を揃えて比較させる。

制度・規格等は本文末尾の参考資料も確認してください。

JSFiddleでコードを試す

JSFiddleは、ブラウザーでHTML・CSS・JavaScriptを入力して実行できるサービスです。短い動作確認から始められます。

1. 新しい編集画面を開きます。JavaScriptは通常のJavaScriptを選び、外部ライブラリは追加しません。
2. HTML欄にはページの本文、CSS欄には見た目、JavaScript欄には処理を書きます。HTML欄に<html>や<body>は不要です。JavaScript欄に<script>は付けません。
3. DOMを使う例では、JavaScriptの実行タイミングを「On Load」「On DOM Ready」または「No wrap - bottom of body」にします。
4. 「Run」を押してResult欄を確認します。書き換えたら再びRunを押します。

console.logの結果は通常、ページではなく開発者ツールのコンソールに出ます。このサイトの計算例をResult欄で読みたいときは、HTML欄に次を入れます。

<pre id="output"></pre>

JavaScript欄には次を入れ、console.log(2 + 3);の行を、試したいコード一つに置き換えます。独立した例を複数まとめて貼らないでください。

{
  const output = document.getElementById("output");
  const console = {
    log(...values) {
      output.textContent += values.join(" ") + "\n";
    }
  };
  console.log(2 + 3);
}

Runを押すと「5」と表示されます。外側の波括弧の中だけで表示用のconsoleを用意しているため、ブラウザー本来のコンソールは変更しません。

HTMLとJavaScriptの両方を載せた実習例は、この表示用コードで囲まず、それぞれの欄へ分けて貼り付けます。保存・共有時は公開範囲を確認し、個人情報やパスワードを入力しないでください。コードは手元にも残しましょう。

NAS・GitHub・CodePenなど、作業環境の選び方

この単元でできるようになること

• 線形探索と二分探索の手順と前提を説明できる。
• 整列で比較と交換が果たす役割を追える。
• データ件数と処理量の増え方を関連付けられる。

ナビのひとこと

番号札を探すとき、一枚ずつ見る方法と中央から絞る方法があるね。どちらも、同じ並びで使えるのかな？

探索は、見つからない場合まで設計する

探索は、条件に合うデータやその位置を求める処理である。架空の道具貸出所の番号札を考える。札が無順序でも、先頭から一つずつ比べる線形探索なら使える。見つかったときの位置だけでなく、最後までなかったときの結果も決める必要がある。

線形探索で最初の位置を返す

function linearSearch(values, target) {
  for (let i = 0; i < values.length; i++) {
    if (values[i] === target) return i;
  }
  return -1;
}
const cards = [14, 6, 21, 6];
console.log(linearSearch(cards, 6));
console.log(linearSearch(cards, 9));
console.log(linearSearch([], 6));

出力は 1、-1、-1。同じ番号が複数あれば、最初に見つけた位置を返す。添字は零から始まるため、先頭の位置は0であり、「見つからない」を0で表すと区別できない。この教材では、有効な添字ではない-1を使うと定めた。

二分探索は、整列済みが前提

昇順に並んだ配列なら、中央の値と目標を比較できる。目標が中央より大きければ、中央以下の範囲に目標はないので、右側だけを残す。小さければ左側を残す。探索範囲を半分ほどに絞る操作を繰り返すのが二分探索である。

昇順の配列を二分探索する

function binarySearch(values, target) {
  let low = 0;
  let high = values.length - 1;
  while (low <= high) {
    const middle = Math.floor((low + high) / 2);
    if (values[middle] === target) return middle;
    if (values[middle] < target) {
      low = middle + 1;
    } else {
      high = middle - 1;
    }
  }
  return -1;
}
const cards = [4, 9, 15, 23, 31, 42, 58];
console.log(binarySearch(cards, 4), binarySearch(cards, 58));
console.log(binarySearch(cards, 22), binarySearch([], 4));

出力は 0 6、-1 -1。中央を調べた後、次の範囲から中央自身を除くことが大切だ。middle + 1 や middle - 1 を忘れると、一要素の範囲で変化しなくなる場合がある。重複がある配列では、この関数は一致するどれかの位置を返し、必ず先頭の位置になるとは限らない。

ナビのひとこと

半分を捨ててよいのは、並び順が分かっているから。速い手順には、それを支える前提があるんだね。

選択整列は、未確定部分から最小を選ぶ

整列は、データを決めた順序に並べる処理である。選択整列では、まだ位置が確定していない部分の最小値を探し、その先頭と交換する。最初の一回で最小値の位置が確定し、二回目ではその次が確定する。確定済みの範囲を広げる見方が重要だ。

最小値を選んで交換する

const values = [8, 3, 5, 1];
let comparisons = 0;
for (let i = 0; i < values.length - 1; i++) {
  let minimum = i;
  for (let j = i + 1; j < values.length; j++) {
    comparisons++;
    if (values[j] < values[minimum]) minimum = j;
  }
  const saved = values[i];
  values[i] = values[minimum];
  values[minimum] = saved;
  console.log(values.join(","));
}
console.log(comparisons);

出力は 1,3,5,8 が三行、その後 6。この並びでは最初の交換だけで全体が昇順になるが、手順はそれを知らないので、残りの最小値の確認を続ける。比較回数は三回、二回、一回の合計で六回となる。「画面上でもう並んで見える」と「必要な検査が終わった」は異なる。

隣り合う要素を交換する整列

バブルソートは、隣り合う要素の順序が逆なら交換する方法である。左から右へ比較すると、一巡で最大の値が右端へ移動する。次の巡回では確定した右端を除くことができる。途中で一度も交換しなかったら終了する改良も考えられる。

観点	線形探索	二分探索	選択整列
事前の整列	不要	必要	整列自体を行う
主な操作	先頭から比較	中央と比較し範囲を縮小	最小を探して交換
件数が増えたとき	最悪の比較回数は件数に比例	比較回数はゆっくり増加	比較回数はおよそ件数の二乗に比例

二分探索が一回ごとに範囲を半減するのに対し、選択整列の比較は、件数から一を引いた数から一までを足す。件数が二倍になると、後者の比較回数は大きな件数ではおよそ四倍になる。こうした増え方を計算量として捉える。

一度だけ探すために、時間をかけて整列するのが得とは限らない。何度も同じ集合を検索するのか、追加や削除が頻繁なのか、元の順序を残す必要があるかで選択は変わる。比較回数と、実機で測る実行時間も同じ量ではない。

注意： 二分探索に未整列の配列を渡しても、実行時エラーになるとは限らず、答えを見失う場合がある。整列例は元配列を変更する。また同値のデータの順序まで保存したい場合は、整列の安定性も検討しよう。

用語

用語	意味
線形探索	要素を順に調べる探索
二分探索	整列済みの範囲を二分しながら探す方法
選択整列	未確定部分の最小値などを選んで配置する方法
バブルソート	隣接要素を比較・交換する整列
計算量	入力の大きさに対して必要な処理量がどう増えるかという見方

確認問題

1. 線形探索の配列で21を探すと、何回目の比較で見つかり、どの添字を返すか。
2. 二分探索の配列で22を探すとき、調べる中央の値を順に挙げよう。
3. 五要素をこの選択整列で並べる場合の比較回数を求め、すでに昇順でも同じか説明しよう。

問1の解答例を見る

三回目の比較で見つかり、添字2を返す。先頭から14、6、21の順に調べる。

問2の解答例を見る

23、9、15の順に調べる。その後、探索区間が空になり、22は見つからず−1を返す。

問3の解答例を見る

4＋3＋2＋1＝10回。掲載した選択整列は、既に昇順でも未確定部分を全て比較して最小値を探すため、比較回数は同じである。

まとめ

ナビのひとこと

前提、見つからない場合、件数が増えたとき。この三点で比べると、手順を選ぶ理由が明確になるね。

参考

• 文部科学省：高等学校学習指導要領 情報科関係資料
• MDN：JavaScriptガイド