線形探索と二分探索の違いとは？JavaScriptで使い分けを解説

線形探索と二分探索は、どちらもデータの中から目的の値を探すための代表的な探索アルゴリズムです。線形探索は、配列の先頭から順番に値を確認していく方法です。データが整列されていなくても使えるため、非常にシンプルで柔軟です。一方、二分探索は、整列済みのデータに対して中央の値を確認し、探索範囲を半分ずつ狭めていく方法です。条件はありますが、大量データに対して非常に高速に動作します。

JavaScriptでは、実務で探索処理を書く場合、includes()、find()、findIndex()などの標準メソッドを使うことが多いです。これらは線形探索に近い考え方で動くことが多く、コードも読みやすくなります。一方で、整列済みの大量データを何度も検索する場合には、二分探索の考え方が役立ちます。本記事では、線形探索と二分探索の仕組み、条件、計算量、JavaScriptコード、メリット・デメリット、実務での使い分けを分かりやすく比較します。

1. 線形探索と二分探索の概要

線形探索は、データを先頭から順番に確認して、目的の値や条件に一致する要素を探す方法です。たとえば、[5, 3, 8, 1]から8を探す場合、5、3、8の順に確認し、8を見つけた時点で終了します。配列がどのような順番で並んでいても使えるため、最も基本的で扱いやすい探索アルゴリズムです。

二分探索は、整列済みの配列に対して使う高速な探索アルゴリズムです。昇順に並んだ配列の中央を確認し、目的の値が中央より小さければ左側、大きければ右側を探します。この処理を繰り返すことで、探索範囲を半分ずつ減らします。データが整列されているという条件はありますが、大量データでは線形探索より大幅に効率的です。

1.1 線形探索の特徴

線形探索の特徴は、前提条件が少ないことです。配列が整列されていなくても使えますし、数値だけでなく文字列やオブジェクト配列にも応用しやすいです。条件が複雑な場合でも、if文やコールバック関数で柔軟に書けます。

一方で、データ量が増えると確認回数も増えます。目的の値が末尾にある場合や存在しない場合は、すべての要素を確認する必要があります。そのため、大量データを何度も検索する場合には効率が悪くなることがあります。

1.2 二分探索の特徴

二分探索の特徴は、探索範囲を半分ずつ狭められることです。これにより、時間計算量はO(log n)になります。大量データでは非常に効率的で、整列済み配列から値を探す場合に強力です。

ただし、二分探索は整列済みデータでなければ使えません。未整列の配列に使うと、正しい結果を得られません。また、left、right、midの境界管理を間違えるとバグが出やすいため、実装には注意が必要です。

2. 使用条件の違い

線形探索と二分探索の最も大きな違いは、使用条件です。線形探索は、データがどのような順番でも使えます。配列が整列されていなくても問題ありません。APIから取得したままのデータ、ユーザーが入力した順番のデータ、ランダムな並びのデータでも、そのまま先頭から順番に確認できます。

二分探索は、データが整列済みであることが必須です。昇順や降順など、一定のルールで並んでいるからこそ、中央の値を見て左側または右側を捨てる判断ができます。整列されていないデータでは、中央より小さい値が右側にある可能性もあるため、半分を捨てることができません。

2.1 線形探索は未整列データでも使える

線形探索は、未整列データに対してそのまま使えます。これは非常に大きな利点です。たとえば、商品一覧が登録順に並んでいる場合でも、ユーザー一覧が更新順に並んでいる場合でも、条件に合う要素を先頭から探せます。

そのため、実務では線形探索の考え方がよく使われます。find()やfilter()を使えば、整列されていないオブジェクト配列からでも条件に合うデータを簡単に取り出せます。

2.2 二分探索は整列済みデータが必要

二分探索では、探索対象が整列されている必要があります。昇順配列なら、中央より小さい値は左側、大きい値は右側にあるという前提が成り立ちます。この前提があるからこそ、探索範囲を半分にできます。

もし未整列データに二分探索を使いたい場合は、まずソートが必要です。ただし、ソートにはコストがかかるため、1回だけ検索するなら線形探索の方が効率的な場合もあります。二分探索は、整列済みデータを何度も検索する場面で特に有効です。

3. 動作の違い

線形探索は、先頭から順番に確認します。1つ目、2つ目、3つ目というように、目的の値に到達するまで直線的に進みます。条件に一致した時点で処理を終了できますが、見つからない場合は最後まで確認します。非常に分かりやすい動きで、コードも簡単です。

二分探索は、中央を確認して探索範囲を半分にします。目的の値が中央より小さいなら左側、大きいなら右側に絞ります。この処理を繰り返すことで、確認する範囲が急速に小さくなります。動きは線形探索より複雑ですが、大量データでは非常に効率的です。

3.1 線形探索の動作

線形探索では、配列を順番に走査します。たとえば、[2, 9, 4, 7]から7を探す場合、2、9、4、7の順に確認します。目的の値が最後にあるため、4回の比較が必要です。

目的の値が先頭にあれば1回で済みますが、位置が後ろになるほど比較回数が増えます。存在しない値を探す場合は、すべての要素を確認します。単純ですが、データ量が多いと重くなりやすいです。

3.2 二分探索の動作

二分探索では、[1, 3, 5, 7, 9, 11, 13]のような整列済み配列を使います。7を探す場合、中央の7を確認してすぐ見つかります。もし11を探すなら、中央の7より大きいので右側だけを探し、次の中央で11を確認します。

このように、二分探索では毎回半分の範囲を捨てます。確認する要素数が大幅に減るため、データ量が大きくなるほど線形探索との差が広がります。

4. 計算量の比較

線形探索の時間計算量はO(n)です。データ数がn個ある場合、最悪ではn個すべてを確認します。目的の値が先頭にあれば速いですが、末尾にある場合や存在しない場合は確認回数が多くなります。データ量に比例して処理時間が増えるため、大量データでは注意が必要です。

二分探索の時間計算量はO(log n)です。1回の比較ごとに探索範囲を半分にするため、データ量が増えても比較回数はゆるやかにしか増えません。100万件のデータでも、整列済みであれば20回程度の比較で探せる場合があります。この違いが、二分探索の大きな強みです。

4.1 O(n)の意味

O(n)は、データ量に比例して処理が増えることを意味します。10件なら最大10回、1000件なら最大1000回、100万件なら最大100万回の確認が必要になる可能性があります。線形探索はこの性質を持っています。

小さなデータではO(n)でも問題にならないことが多いです。しかし、大量データを何度も検索する場合は、積み重なって大きな負荷になります。検索回数が多い場合は、データ構造を変えることも検討しましょう。

4.2 O(log n)の意味

O(log n)は、データ量が増えても処理回数が非常にゆるやかに増えることを意味します。二分探索では、1回ごとに探索範囲が半分になります。そのため、データ数が2倍になっても、必要な比較回数は1回増える程度です。

この性質は、大量データに対して非常に有効です。ただし、二分探索を使うには整列済みデータが必要です。ソートコストも含めて考える必要があります。

5. JavaScriptコードの比較

JavaScriptで線形探索を書く場合、for文で先頭から順番に確認する方法が基本です。標準メソッドを使うならincludes()、find()、findIndex()などが利用できます。コードは短く、条件も書きやすいため、実務では線形探索に近い標準メソッドがよく使われます。

二分探索は、left、right、midを使って探索範囲を管理します。コードは線形探索より少し複雑ですが、整列済みデータに対して高速に動作します。ここでは、どちらもインデックスを返し、見つからない場合は-1を返す形で比較します。

5.1 線形探索のコード

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

  return -1;
}

console.log(linearSearch([1, 3, 5, 8, 10], 8)); // 3

線形探索は非常に読みやすいです。配列が整列されている必要もありません。小さなデータや単発の検索では、このような考え方で十分です。

5.2 二分探索のコード

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

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

    if (array[mid] === target) {
      return mid;
    }

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

  return -1;
}

console.log(binarySearch([1, 3, 5, 8, 10], 8)); // 3

二分探索は、配列が昇順に整列されていることが前提です。条件が合えば非常に高速ですが、未整列の配列には使えません。

6. 線形探索を使うべき場面

線形探索を使うべき場面は、データ量が少ない場合、配列が整列されていない場合、検索条件が複雑な場合です。JavaScriptの実務では、オブジェクト配列から条件に合う要素を探すことが多く、このような場合はfind()やfilter()による線形探索が自然です。コードも読みやすく、保守しやすいです。

また、1回だけ検索する場合も線形探索で十分なことが多いです。二分探索を使うためにソートするコストを考えると、未整列データをそのまま探した方が簡単で効率的な場合があります。線形探索は最も基本的な方法ですが、実務でも非常に出番が多い探索方法です。

6.1 条件が複雑な場合

オブジェクト配列では、単純な数値比較だけでなく、複数条件を組み合わせて探すことがあります。たとえば、roleがadminで、activeがtrueのユーザーを探すような場合です。このような検索は、線形探索の方が書きやすいです。

const user = users.find(item => item.role === "admin" && item.active);

二分探索は、整列された1つの基準に沿って探すのが得意です。複雑な条件検索では、線形探索やfilter()の方が自然です。

6.2 データが小さい場合

データが小さい場合は、線形探索で十分です。たとえば、10件や20件程度の配列であれば、二分探索を実装するメリットはほとんどありません。むしろ、コードの分かりやすさを優先した方がよいです。

実務では、必要以上に複雑なアルゴリズムを使うと保守性が下がることがあります。小規模データでは、find()やincludes()を使った素直な実装が適しています。

7. 二分探索を使うべき場面

二分探索を使うべき場面は、データが整列済みで、データ量が多く、検索回数が多い場合です。たとえば、昇順に並んだ数値IDの一覧から何度もIDを探す場合、二分探索は有効です。線形探索では毎回多くの要素を確認する可能性がありますが、二分探索なら比較回数を大幅に減らせます。

また、二分探索は完全一致だけでなく、境界を探す問題にも向いています。target以上になる最初の位置や、条件を満たす最小値を探すような場面では、二分探索の考え方が役立ちます。大量データやアルゴリズム問題では、二分探索は非常に重要な選択肢です。

7.1 整列済みデータを何度も検索する場合

すでに整列済みのデータがあり、それに対して何度も検索するなら、二分探索は効果的です。最初からID順に並んでいるデータや、時系列で管理されているデータなどでは、探索範囲を半分にできる可能性があります。

ただし、データが頻繁に追加・削除され、整列状態を保つのが難しい場合は注意が必要です。整列状態の維持にもコストがかかるため、全体の設計として考える必要があります。

7.2 境界探索が必要な場合

二分探索は、境界探索にも使えます。たとえば、配列の中で特定の値以上になる最初の位置を探す場合や、条件を満たす最小の値を探す場合です。これは線形探索でも可能ですが、大量データでは二分探索の方が効率的です。

境界探索は完全一致より少し難しいですが、二分探索の応用として非常に重要です。アルゴリズム学習を進めるなら、基本の二分探索を理解したあとに学ぶとよいでしょう。

8. 比較表で整理する

線形探索と二分探索の違いを整理すると、それぞれの向き不向きが分かりやすくなります。線形探索は、条件が少なく、未整列データにも使え、コードが簡単です。一方、二分探索は、整列済みデータが必要ですが、O(log n)で高速に検索できます。どちらが優れているかではなく、状況に応じて選ぶことが重要です。

以下のように比較すると、選び方が明確になります。実務では、まず標準メソッドでシンプルに書き、データ量や検索回数が問題になったときに、二分探索やMap、Setなどの方法を検討するのが現実的です。

8.1 比較表

8.2 比較から分かること

線形探索は、汎用性が高く、実装も簡単です。データが小さい場合や条件が複雑な場合には非常に使いやすいです。JavaScriptの標準メソッドとも相性が良く、実務で自然に使われます。

二分探索は、条件が整っている場合に非常に高速です。整列済みデータを大量に扱う場合や、境界探索が必要な場合には強力です。ただし、整列条件や境界更新を正しく管理する必要があります。比較表を見ながら、どちらが現在のデータに合っているかを判断しましょう。

9. 実務での選び方

JavaScriptの実務では、まず読みやすく標準的な方法を選ぶことが大切です。小さな配列や単純な検索では、includes()やfind()を使うだけで十分です。無理に二分探索を実装すると、コードが複雑になり、バグの原因になることがあります。アルゴリズムの速さだけでなく、保守性も重要です。

一方で、データ量が多く、検索回数が多い場合には、探索方法を見直す価値があります。整列済みデータなら二分探索、存在確認が多いならSet、キーから値を取得するならMapが有効です。実務では、線形探索と二分探索だけでなく、データ構造全体を含めて考えることが重要です。

9.1 まず標準メソッドを使う

通常は、find()、includes()、filter()などを使うのが自然です。コードが短く、意図も伝わりやすいです。たとえば、ユーザーIDで1件探すならfind()で十分な場合が多いです。

const user = users.find(item => item.id === targetId);

この書き方は線形探索に近いですが、小規模データや通常のUI処理では十分実用的です。まずはシンプルに書き、問題が出たら最適化を考えましょう。

9.2 ボトルネックになったら見直す

検索処理が重いと感じた場合は、まず計測しましょう。console.time()やDevToolsを使って、本当に検索が遅いのか、レンダリングや通信が原因なのかを確認します。原因が検索にある場合は、MapやSet、二分探索、サーバー側検索などを検討します。

パフォーマンス改善では、アルゴリズムを変えるだけでなく、データの持ち方を変えることが重要です。何度も検索するなら、最初に検索しやすい形へ変換することで、全体の処理を軽くできます。

おわりに

線形探索と二分探索は、どちらも重要な探索アルゴリズムです。線形探索は、先頭から順番に確認するシンプルな方法で、未整列データにも使えます。実装が簡単で、JavaScriptのfind()、includes()、filter()などの標準メソッドとも関係が深いため、実務でもよく使われます。一方、二分探索は、整列済みデータに対して探索範囲を半分ずつ狭める方法で、大量データに対して非常に高速です。

両者の違いは、使用条件と計算量にあります。線形探索はO(n)で、条件が少なく柔軟です。二分探索はO(log n)で高速ですが、整列済みデータが必要です。小さな配列や複雑な条件検索では線形探索が向いており、整列済みの大量データを何度も検索する場合は二分探索が向いています。

JavaScriptの実務では、まず標準メソッドを使って読みやすく書くことが基本です。そのうえで、データ量や検索回数が増えて問題になった場合に、二分探索、Map、Set、サーバー側検索などを検討しましょう。線形探索と二分探索の違いを理解しておくことで、データ検索をより効率的に設計できるようになります。