はじめに: 線形探索はアルゴリズムの基本をつかむ入口
基本情報処理技術者試験でアルゴリズムを学ぶとき、最初に押さえておきたい考え方のひとつが「探索」です。
探索とは、たくさんのデータの中から目的の値を探す処理です。ユーザーIDを探す、商品一覧から特定の商品を探す、配列の中に目的の値があるか確認する。実務のコードでも、形を変えて何度も出てきます。
その中でも線形探索は、データを先頭から順番に調べる最も素直な探索方法です。特別な準備がいらないため、アルゴリズムの流れを理解する入口として向いています。
この記事では、JavaScriptの配列を使って線形探索を実装しながら、「見つかったら終了する」「見つからない場合は最後まで調べる」「データ数が増えると処理回数も増える」といった基本を確認していきます。
線形探索とは何か
線形探索とは、配列やリストの要素を先頭から1つずつ確認して、目的の値を探す方法です。
たとえば、次のような配列から 21 を探すとします。
[12, 35, 8, 21, 5]線形探索では、まず 12 を確認し、次に 35、その次に 8、そして 21 を確認します。目的の値が見つかったら、その時点で探索を終了します。
もし最後まで見ても目的の値がなければ、「見つからなかった」と判断します。
線形探索の特徴は、データが整列されていなくても使えることです。小さい順や大きい順に並んでいなくても、先頭から順番に見ていけば探せます。そのぶん、データが多い場合は確認回数が増えやすいという弱点もあります。
JavaScriptで線形探索を実装する
JavaScriptで線形探索を書くと、基本は for 文で配列を先頭から順に調べる形になります。
function linearSearch(array, target) {
for (let i = 0; i < array.length; i++) {
if (array[i] === target) {
return i;
}
}
return -1;
}
const numbers = [12, 35, 8, 21, 5];
const index = linearSearch(numbers, 21);
console.log(index);このコードでは、linearSearch 関数に配列と探したい値を渡しています。
配列の中を先頭から順に確認し、array[i] === target が成り立ったら、その位置を表すインデックス i を返します。今回の例では 21 は4番目の要素なので、インデックスとしては 3 が返ります。
最後まで調べても見つからない場合は -1 を返します。JavaScriptの indexOf() も、値が見つからないときに -1 を返します。ここでは便利なメソッドを使う前に、自分で処理を書いて仕組みを理解していると考えるとよいでしょう。
見つかる場合と見つからない場合を比べる
線形探索では、目的の値がどこにあるかによって、調べる回数が変わります。
先頭の要素で見つかれば、1回の確認で終わります。末尾にあれば、ほとんどすべての要素を確認する必要があります。配列の中に存在しなければ、最後まで調べてから「見つからなかった」と判断します。
確認回数を数えると、処理の流れが見えやすくなります。
function linearSearchWithCount(array, target) {
let count = 0;
for (let i = 0; i < array.length; i++) {
count++;
if (array[i] === target) {
return { index: i, count };
}
}
return { index: -1, count };
}
const numbers = [12, 35, 8, 21, 5];
console.log(linearSearchWithCount(numbers, 12));
console.log(linearSearchWithCount(numbers, 21));
console.log(linearSearchWithCount(numbers, 99));12 は先頭にあるので、確認回数は少なくなります。21 は途中で見つかります。99 は配列にないため、最後まで確認します。
このように、線形探索は「見つかったら途中で終わる」こともあれば、「見つからずに最後まで進む」こともあります。
線形探索の計算量を理解する
アルゴリズムを考えるときは、データ数が増えたときに処理がどれくらい増えるかを見ます。この考え方を計算量と呼びます。
線形探索では、要素数が n 個あるとき、最悪の場合は n 回確認します。目的の値が最後にある場合や、そもそも存在しない場合は、すべての要素を見る必要があるからです。
このような処理は、オーダ記法で O(n) と表します。
基本情報の学習では、最初から厳密な数学として覚えるよりも、「データ数に比例して確認回数が増える」と理解すると十分です。データが10個なら最大10回、100個なら最大100回、10000個なら最大10000回確認する可能性があります。
線形探索は単純で分かりやすい一方、データが大きくなると効率が問題になることがあります。この感覚が、次に二分探索やハッシュ表を学ぶときの土台になります。
試験ではどう問われるか
基本情報処理技術者試験では、線形探索はアルゴリズムのトレース問題として出てきやすいテーマです。
たとえば、配列を先頭から順に見ていき、目的の値が見つかったときに何番目で止まるかを問われることがあります。また、目的の値がない場合に何回比較するか、最悪の場合の計算量がどうなるかを考える問題にもつながります。
試験対策としては、次の点を押さえておくと整理しやすくなります。
- 先頭から順番に調べる
- 見つかったらその時点で終了する
- 見つからない場合は最後まで調べる
- 最悪の場合の計算量は
O(n) - 整列済みデータを前提にする二分探索とは違う
特に、ループの終了条件と、見つかったときに処理を止める条件を読み取ることが大切です。
実務ではどう使われるか
実務のJavaScriptでは、毎回自分で for 文を書いて線形探索を実装するとは限りません。
たとえば、配列の中から条件に合う要素を探すなら find()、位置を知りたいなら findIndex()、含まれているかだけを知りたいなら includes() や some() が使えます。
const users = ['Alice', 'Bob', 'Carol'];
console.log(users.includes('Bob'));
console.log(users.find((name) => name.startsWith('C')));これらのメソッドも、配列を順に確認するという意味では線形探索に近い考え方で理解できます。
ただし、データが大量になる場合は注意が必要です。毎回すべての要素を順番に調べると、処理が重くなることがあります。その場合は、データの持ち方を変えたり、検索しやすい構造を使ったり、サーバー側やデータベースで絞り込んだりします。
まずは単純な方法を理解し、必要になったらより効率のよい方法を考える。この順番で学ぶと、アルゴリズムの知識が実務の判断にもつながります。
まとめ: 線形探索は「順番に調べる」基本のアルゴリズム
線形探索は、配列やリストを先頭から順に調べて、目的の値を探すアルゴリズムです。データが整列されていなくても使えるため、考え方はとてもシンプルです。
一方で、最悪の場合はすべての要素を確認する必要があります。そのため、計算量は O(n) と表されます。
JavaScriptで自分で実装してみると、配列、ループ、条件分岐、戻り値、計算量の考え方がつながって見えてきます。基本情報のアルゴリズム対策としても、実務で配列処理を読むための基礎としても、まず押さえておきたい探索方法です。
次に学ぶなら、整列済みのデータを効率よく探す二分探索に進むと、探索アルゴリズムの違いがさらに分かりやすくなります。
コメント