EN
JP
KR線形探索とは？JavaScriptでLinear Searchを実装する方法を解説
線形探索は、探索アルゴリズムの中でも最も基本的な方法です。配列やリストの先頭から順番に要素を確認し、目的の値や条件に一致する要素を見つけるまで処理を続けます。英語ではLinear Searchと呼ばれ、日本語では線形探索または逐次探索と呼ばれます。仕組みが非常にシンプルで、データが並び替えられている必要もないため、アルゴリズム学習の入門としてよく扱われます。
JavaScriptでは、線形探索の考え方は多くの標準メソッドに関係しています。たとえば、includes()は配列の中に値が含まれているかを確認し、find()は条件に一致する最初の要素を返し、findIndex()は条件に一致する最初の位置を返します。これらのメソッドは便利ですが、基本的には先頭から順番に確認していく探索と考えることができます。本記事では、線形探索の仕組み、JavaScriptでの実装方法、最初の一致やすべての一致を探す方法、計算量、メリット・デメリット、実務での使い分けまで詳しく解説します。
1. 線形探索とは？
線形探索とは、データを先頭から順番に確認して、目的の値や条件に合う要素を探す探索アルゴリズムです。たとえば、[10, 20, 30, 40]という配列から30を探す場合、最初に10を確認し、次に20を確認し、その次に30を見つけます。このように、目的の値に到達するまで順番に見ていくため、非常に直感的で理解しやすい方法です。
線形探索は、配列が昇順や降順に並んでいる必要がありません。これは大きな利点です。二分探索のような高速な方法は、データが整列済みであることが前提になりますが、線形探索はどのような順番のデータにも使えます。そのため、実務でも小さな配列や一時的なデータ、条件が複雑な検索では、線形探索に近い方法がよく使われます。
1.1 線形探索の基本イメージ
線形探索の基本は、「見つかるまで順番に確認する」ことです。配列の先頭から1つずつ値を取り出し、探している値と一致するかを確認します。一致したらその時点で探索を終了し、位置や要素を返します。最後まで確認しても見つからなければ、見つからなかったことを示す値を返します。
この流れは、人間がリストから項目を探すときの動きに近いです。小さなリストであれば、先頭から順番に見てもほとんど問題ありません。しかし、リストが非常に大きくなると、目的の値が後ろにある場合や存在しない場合に、多くの確認が必要になります。線形探索は分かりやすい反面、データ量が増えたときの効率には注意が必要です。
1.2 JavaScript標準メソッドとの関係
JavaScriptには、線形探索に近い動きをする標準メソッドが多くあります。includes()、indexOf()、find()、findIndex()、some()などが代表的です。これらは自分でfor文を書かなくても探索処理を表現できるため、実務ではよく使われます。
たとえば、値が含まれているかを知りたいだけならincludes()、条件に合う要素を取得したいならfind()、条件に合う位置を知りたいならfindIndex()を使います。内部的な考え方を理解しておくと、どのメソッドを使うべきか判断しやすくなります。
2. 線形探索の基本的な考え方
線形探索では、探索対象のデータを1つずつ確認します。配列であれば、インデックス0から始めて、array[0]、array[1]、array[2]というように順番に見ていきます。探している値と一致したら、その位置や値を返します。条件に一致しない場合は次の要素へ進みます。配列の最後まで確認しても見つからなければ、-1やnull、undefinedなど、見つからなかったことを表す値を返します。
このアルゴリズムでは、データの並び順を前提にしません。そのため、整列されていない配列や、ランダムな順番のデータにも使えます。また、検索条件を自由に書きやすい点も特徴です。単純な数値一致だけでなく、オブジェクトのプロパティ、複数条件、文字列の部分一致などにも応用できます。
2.1 一致したらすぐ終了する
線形探索では、目的の値が見つかった時点で処理を終了できます。これは重要なポイントです。たとえば、最初の要素で見つかれば、残りの要素を確認する必要はありません。find()やsome()も、条件を満たす要素が見つかるとそこで処理を終えます。
この性質により、目的の値が前の方にある場合は比較的速く処理できます。一方で、目的の値が最後にある場合や存在しない場合は、すべての要素を確認する必要があります。線形探索のパフォーマンスは、データ量だけでなく、目的の値がどの位置にあるかにも影響されます。
2.2 条件検索にも使える
線形探索は、単純な値の一致だけでなく、条件検索にも向いています。たとえば、ユーザー一覧から年齢が20以上の最初のユーザーを探す、商品一覧から在庫がある商品を探す、記事一覧から特定のカテゴリに属する記事を探すといった処理です。
JavaScriptでは、find()を使うことでこのような条件検索を簡潔に書けます。線形探索を自作する場合でも、if文の中に条件を書くだけなので理解しやすいです。条件が複雑な場合や、データが整列されていない場合は、線形探索が自然な選択になります。
3. いつ線形探索を使うのか
線形探索は、データ量が少ない場合、データが整列されていない場合、検索条件が複雑な場合に向いています。たとえば、数十件程度の配列から条件に合う要素を探すだけであれば、線形探索で十分です。わざわざデータをソートしたり、複雑なデータ構造に変換したりするよりも、find()やincludes()を使って素直に書く方が読みやすくなります。
また、1回だけ検索する場合にも線形探索は適しています。二分探索を使うにはデータが整列済みである必要があり、整列していない配列ならソートのコストが発生します。1回の検索のためだけにソートするより、線形探索でそのまま探した方が効率的なこともあります。探索方法は、単純な計算量だけでなく、データの状態や検索回数を考えて選ぶことが大切です。
3.1 小規模データの場合
小規模データでは、線形探索は非常に実用的です。要素数が少なければ、先頭から順番に確認しても処理時間はほとんど問題になりません。むしろ、複雑なアルゴリズムを使うより、標準メソッドを使って分かりやすく書く方が保守性の面で有利です。
たとえば、メニュー項目、権限リスト、タグ一覧、選択肢の配列などは、データ量がそれほど多くないことが多いです。このような場面では、includes()やfind()で十分です。過剰な最適化を避け、読みやすさを優先することも実務では重要です。
3.2 整列されていないデータの場合
線形探索は、データが整列されていなくても使えます。これは二分探索との大きな違いです。たとえば、APIから取得した順番のままのデータや、ユーザーが入力した順番を保つ必要があるデータでは、二分探索のために並び替えると元の意味が失われる場合があります。
このような場合は、線形探索でそのまま条件に合う要素を探す方が自然です。特に、オブジェクト配列から複雑な条件で探す場合は、ソートよりもfind()やfilter()の方が扱いやすいです。データの順序を変えたくない場合にも、線形探索は安全な方法です。
4. JavaScriptで線形探索を書く方法
JavaScriptで線形探索を書く方法は大きく分けて2つあります。1つはfor文を使って自分で探索処理を書く方法です。もう1つは、find()、findIndex()、includes()などの標準メソッドを使う方法です。アルゴリズム学習ではfor文で書くと仕組みを理解しやすく、実務では標準メソッドを使うとコードが簡潔になります。
線形探索を自作する場合は、戻り値をどうするかを決めることが重要です。値が見つかったらインデックスを返すのか、要素そのものを返すのか、trueまたはfalseを返すのかによって関数の設計が変わります。目的に合わせて戻り値を決めることで、使いやすい探索関数になります。
4.1 インデックスを返す実装
目的の値が見つかった位置を返したい場合は、インデックスを返す実装にします。見つからなかった場合は-1を返すと、indexOf()と似た使い方ができます。
function linearSearch(array, target) { for (let i = 0; i < array.length; i++) { if (array[i] === target) { return i; } } return -1;}console.log(linearSearch([4, 2, 7, 1], 7)); // 2console.log(linearSearch([4, 2, 7, 1], 9)); // -1
この実装はシンプルですが、線形探索の基本を理解するには十分です。配列の先頭から順番に確認し、一致したらすぐ返すという流れが明確に表れています。
4.2 要素そのものを返す実装
オブジェクト配列では、インデックスよりも要素そのものが必要なことがあります。その場合は、条件に一致した要素を返す関数にします。JavaScriptのfind()に近い考え方です。
function findUserById(users, targetId) { for (const user of users) { if (user.id === targetId) { return user; } } return undefined;}const users = [ { id: 1, name: "Sato" }, { id: 2, name: "Tanaka" }];console.log(findUserById(users, 2)); // { id: 2, name: "Tanaka" }
実務では、このような処理はusers.find(user => user.id === targetId)と書くことが多いです。ただし、自作してみることで、find()がどのような流れで動いているのかを理解できます。
5. 最初に一致する要素を探す
線形探索では、最初に条件に一致した要素を見つけた時点で処理を終了できます。これは、1件だけ必要な場合に効率的です。たとえば、ユーザーIDは一意であることが多いため、IDが一致するユーザーを1件見つけたら、それ以上検索を続ける必要はありません。このような場面では、find()やfindIndex()が向いています。
最初に一致する要素を探す処理は、検索結果が1つだけでよい場合に使います。条件を満たす要素が複数ある可能性があり、それらをすべて取得したい場合はfilter()を使う必要があります。線形探索では、目的に応じて「最初の1件で止める」のか「最後まで探す」のかを使い分けることが重要です。
5.1 findを使う方法
find()は、条件に一致する最初の要素を返します。見つからなかった場合はundefinedを返します。オブジェクト配列から特定の条件に合うデータを取り出すときに便利です。
const products = [ { id: 1, name: "Book", price: 1200 }, { id: 2, name: "Pen", price: 200 }];const product = products.find(item => item.id === 2);console.log(product); // { id: 2, name: "Pen", price: 200 }
find()は、条件を満たした時点で処理を止めるため、1件だけ必要な場合に適しています。コードも短く、何を探しているのかが分かりやすいです。
5.2 findIndexを使う方法
要素そのものではなく、位置が必要な場合はfindIndex()を使います。見つかった場合はインデックスを返し、見つからなかった場合は-1を返します。
const scores = [70, 85, 90, 60];const index = scores.findIndex(score => score >= 90);console.log(index); // 2
インデックスが必要になるのは、該当する要素を更新したい場合や、位置に応じた処理を行いたい場合です。要素だけでよいならfind()、位置が必要ならfindIndex()という使い分けが基本です。
6. 一致するすべての位置を探す
線形探索では、最初の1件だけでなく、一致するすべての要素や位置を探すこともできます。たとえば、配列の中に同じ値が複数ある場合、それらのすべての位置を取得したいことがあります。また、文字列やログデータの中で条件に一致する項目をすべて抽出したい場合にも、最後まで探索する必要があります。
この場合は、見つかった時点でreturnせず、結果用の配列に位置や要素を追加していきます。配列の最後まで確認したあと、結果配列を返します。JavaScriptのfilter()は、条件に一致するすべての要素を取得する標準メソッドです。位置も必要な場合は、自分でfor文を書くか、map()とfilter()を組み合わせる方法があります。
6.1 すべてのインデックスを返す
同じ値が複数ある配列から、すべての位置を取得するには、結果用の配列を用意します。一致したらそのインデックスをpushし、最後にまとめて返します。
function findAllIndexes(array, target) { const indexes = []; for (let i = 0; i < array.length; i++) { if (array[i] === target) { indexes.push(i); } } return indexes;}console.log(findAllIndexes([1, 3, 1, 5, 1], 1)); // [0, 2, 4]
この実装では、見つかっても探索を終了しません。すべての位置を取得するために、最後まで確認します。そのため、必ずO(n)の処理になります。
6.2 filterで一致する要素を取得する
要素そのものをすべて取得したい場合は、filter()が便利です。filter()は条件を満たすすべての要素を新しい配列として返します。
const users = [ { name: "Sato", role: "admin" }, { name: "Tanaka", role: "viewer" }, { name: "Suzuki", role: "admin" }];const admins = users.filter(user => user.role === "admin");console.log(admins);
filter()は分かりやすいですが、条件を満たす要素が1件だけ必要な場合にはfind()の方が適しています。filter()は最後まで配列を確認するため、目的に応じて使い分けることが大切です。
7. 線形探索の計算量
線形探索の時間計算量はO(n)です。これは、データ数がn個ある場合、最悪ではn個すべてを確認する必要があるという意味です。目的の値が先頭にあれば1回で見つかりますが、最後にある場合や存在しない場合は、すべての要素を確認します。そのため、データ量が増えるほど処理時間も比例して増えます。
空間計算量は、最初の一致だけを探す場合はO(1)です。追加の大きなデータ構造を作らず、変数だけで処理できるからです。一方、すべての一致を配列に保存する場合は、結果の数に応じて追加メモリが必要になります。線形探索を学ぶときは、時間計算量だけでなく、結果をどのように保存するかによる空間計算量も意識すると理解が深まります。
7.1 最良ケースと最悪ケース
線形探索の最良ケースは、目的の値が配列の先頭にある場合です。この場合、1回の比較で見つかるため、非常に速く処理できます。一方、最悪ケースは、目的の値が配列の末尾にある場合、または存在しない場合です。この場合、すべての要素を確認する必要があります。
平均的には、目的の値がランダムな位置にあるなら、配列の半分程度を確認することになります。ただし、計算量としてはデータ数に比例するためO(n)と表現されます。データ量が少ない場合は問題になりにくいですが、大量データでは注意が必要です。
7.2 二分探索との計算量の違い
線形探索はO(n)、二分探索はO(log n)です。この違いは、データ量が増えるほど大きくなります。たとえば、100万件のデータを探す場合、線形探索では最悪100万回近い確認が必要になりますが、二分探索では条件が整っていれば20回程度の比較で見つけられる場合があります。
ただし、二分探索には整列済みデータが必要です。線形探索は整列されていないデータにも使えるため、前提条件が少ないという強みがあります。計算量だけで判断せず、データの状態や検索回数も含めて選ぶことが大切です。
8. 線形探索のメリット・デメリット
線形探索のメリットは、実装が簡単で、データの並び順に依存しないことです。配列が整列されていなくても使えるため、APIから取得したデータやユーザーが入力した順番のデータにもそのまま適用できます。また、条件検索にも向いており、複雑な条件をif文やコールバック関数で表現しやすいです。
一方で、データ量が増えると処理が重くなりやすい点がデメリットです。毎回先頭から順番に確認するため、大量データを何度も検索する場合には効率が悪くなります。特に、同じ配列に対して何度もID検索を行うような場合は、Mapに変換するなどの工夫を検討した方がよいことがあります。
8.1 メリット
線形探索は、シンプルで理解しやすいことが最大のメリットです。初心者でも処理の流れを追いやすく、アルゴリズム学習の入門に適しています。また、データが整列されている必要がないため、さまざまな場面で使えます。
さらに、検索条件を柔軟に書ける点も強みです。数値の一致だけでなく、文字列の部分一致、オブジェクトのプロパティ条件、複数条件の組み合わせなどにも対応できます。JavaScriptのfind()やfilter()と相性が良く、実務でも自然に使われます。
8.2 デメリット
線形探索のデメリットは、データ量が増えると確認回数が増えることです。小さな配列では問題になりませんが、数万件や数十万件のデータを何度も検索する場合は、パフォーマンスに影響する可能性があります。
また、存在しない値を探す場合は、必ず最後まで確認する必要があります。検索が頻繁に発生する場合は、SetやMapを使って高速に検索できる形に変換することも検討しましょう。線形探索は基本であり便利ですが、大量データでは別の方法との使い分けが重要です。
9. JavaScript実務での使い分け
JavaScriptの実務では、線形探索を自分でfor文で書くよりも、標準メソッドを使うことが多いです。存在確認ならincludes()、最初の一致を取りたいならfind()、位置が必要ならfindIndex()、すべて取得したいならfilter()を使います。これらは線形探索の考え方を分かりやすく表現できるため、コードの可読性も高くなります。
ただし、標準メソッドを使っているからといって、常に高速とは限りません。大量データを毎回find()で検索している場合、内部的には先頭から順番に確認するため、検索回数が増えるほど負荷も増えます。実務では、データ量が少ないなら標準メソッドで十分ですが、検索回数が多いならMapやSetを使うなど、データ構造の見直しも考える必要があります。
9.1 標準メソッドを優先する
通常のコードでは、標準メソッドを使う方が読みやすくなります。for文で線形探索を書くよりも、find()やincludes()を使った方が、何をしたいのかが明確です。チーム開発でも、標準メソッドは他の開発者に意図が伝わりやすいです。
const ids = [1, 2, 3, 5];if (ids.includes(3)) { console.log("ID exists");}
このように、存在確認だけならincludes()で十分です。無理に自作関数を書くより、標準機能を正しく使うことが実務では重要です。
9.2 検索回数が多いならデータ構造を変える
同じデータを何度も検索する場合は、配列のまま線形探索するより、SetやMapを使う方が効率的になることがあります。たとえば、IDの存在確認を何度も行うならSetが便利です。
const idSet = new Set([1, 2, 3, 5]);console.log(idSet.has(3)); // true
最初にSetを作るコストはありますが、その後の検索は高速になります。実務では、1回だけ検索するのか、何度も検索するのかを考えて、配列のまま扱うか、検索用データ構造を作るかを判断しましょう。
おわりに
線形探索は、データを先頭から順番に確認して目的の値や条件に合う要素を探す、最も基本的な探索アルゴリズムです。配列が整列されている必要がなく、実装も非常にシンプルなため、アルゴリズム学習の入門として適しています。JavaScriptでは、includes()、find()、findIndex()、some()、filter()など、多くの標準メソッドが線形探索に近い考え方で使われます。
時間計算量はO(n)であり、データ量が増えるほど確認回数も増えます。そのため、小規模なデータや単発の検索では十分ですが、大量データを何度も検索する場合には、MapやSetなど別のデータ構造を検討することが大切です。線形探索は万能ではありませんが、前提条件が少なく、柔軟に使えるという強みがあります。
実務では、自作の線形探索を毎回書く必要はありません。標準メソッドを正しく使い、必要に応じてデータ構造を見直すことが重要です。線形探索の仕組みを理解しておくと、JavaScriptの配列メソッドがどのように動いているのか、どの場面で重くなりやすいのかを判断しやすくなります。
