Back

JavaScriptでの二分探索の実装

OpenReplay Team OpenReplay Team

Feb 26, 2026 · 2 min read

JavaScriptでの二分探索の実装

10万件の商品価格が格納されたソートされた配列を検索する場合を考えてみましょう。JavaScriptの組み込みメソッドindexOf()は先頭からすべての要素をチェックするため、最大で10万回の比較が必要になります。一方、二分探索ならわずか17回で済みます。この違いこそがJavaScriptの二分探索アルゴリズムが重要である理由であり、自分で実装する価値がある理由です。なぜなら、JavaScriptには二分探索の組み込みメソッドが提供されていないからです。

本記事では、二分探索の仕組み、反復的アプローチと再帰的アプローチの両方の実装方法、そして線形探索と比較してどのような場合に使用すべきかについて解説します。

重要なポイント

  • 二分探索はソート済み配列でのみ動作し、実行時間はO(log n)です。線形探索のO(n)と比較して高速です。
  • ほとんどのユースケースでは反復的アプローチが推奨されます。可読性が高く、効率的で、O(1)の空間計算量で済みます。
  • 再帰的バージョンはエレガントですが、O(log n)のスタック領域を消費します。また、再帰呼び出しにreturnを付け忘れるのはよくあるバグです。
  • 二分探索を適用する前に、必ず数値配列を数値比較関数((a, b) => a - b)でソートしてください。JavaScriptのデフォルトのsort()は辞書順ソートです。

二分探索とは何か、なぜソート済み配列が必要なのか?

二分探索は分割統治法のアルゴリズムです。探索範囲を繰り返し半分に分割することで、目的の値を見つけるか、すべての可能性を使い果たすまで探索を続けます。

ここで重要なのは、ソート済み配列でのみ動作するという点です。このアルゴリズムは、目的の値が中央の要素より大きい場合、右半分に存在するはずだという前提に基づいています。この前提はソートされていないデータでは完全に崩れてしまい、エラーなしに誤った結果を返すことになります。

手順は以下の通りです:

  1. 現在の探索範囲の中央要素を見つける
  2. それが目的の値と等しければ、そのインデックスを返す
  3. 目的の値が小さければ、左半分を探索する
  4. 目的の値が大きければ、右半分を探索する
  5. 見つかるか探索範囲が空になるまで繰り返す

JavaScriptでの二分探索の実装:反復的アプローチ

反復的バージョンはwhileループと2つのポインタを使用します。ほとんどの場合、これが推奨されるアプローチです。可読性が高く、効率的で、O(1)の空間計算量で済みます。

function binarySearch(arr, target) {
  let start = 0
  let end = arr.length - 1

  while (start <= end) {
    const mid = Math.floor((start + end) / 2)

    if (arr[mid] === target) {
      return mid // インデックスを返す
    } else if (arr[mid] < target) {
      start = mid + 1 // 右半分を探索
    } else {
      end = mid - 1 // 左半分を探索
    }
  }

  return -1 // 目的の値が見つからない
}

const prices = [10, 25, 47, 89, 134, 200]
console.log(binarySearch(prices, 89))  // 3
console.log(binarySearch(prices, 50))  // -1

この実装は真偽値ではなく、目的の値のインデックスを返すことに注意してください。実際の使用では、これがほぼ常により有用です。

JavaScriptでの再帰的二分探索

再帰的バージョンは、各呼び出しで更新された境界インデックスを渡します。エレガントですが、O(log n)のスタック領域を使用します。再帰呼び出しごとに1つのフレームが必要になります。

function binarySearchRecursive(arr, target, start = 0, end = arr.length - 1) {
  if (start > end) return -1

  const mid = Math.floor((start + end) / 2)

  if (arr[mid] === target) return mid

  return arr[mid] < target
    ? binarySearchRecursive(arr, target, mid + 1, end)
    : binarySearchRecursive(arr, target, start, mid - 1)
}

const scores = [3, 11, 22, 45, 67, 91]
console.log(binarySearchRecursive(scores, 22))  // 2
console.log(binarySearchRecursive(scores, 50))  // -1

よくあるバグの1つ:再帰呼び出しにreturnを付け忘れることです。これがないと、要素が存在する場合でも関数はundefinedを返してしまいます。

探索前のソート

配列がまだソートされていない場合は、まずソートする必要があります。JavaScriptのデフォルトのArray.sort()は辞書順でソートするため、数値比較が正しく機能しません:

[10, 9, 100].sort()                   // [10, 100, 9] — 誤り
[10, 9, 100].sort((a, b) => a - b)    // [9, 10, 100] — 正しい

二分探索を実行する前に、数値配列には必ず数値比較関数を使用してください。

二分探索 vs 線形探索:どちらをいつ使うべきか

線形探索二分探索
配列のソートが必要不要必要
時間計算量O(n)O(log n)
小さな配列に最適✅❌
大きな配列に最適❌✅
複数回の探索非効率効率的

10,000要素の配列の場合、線形探索は最大10,000回の比較が必要です。二分探索なら最大14回で済みます。小さなソートされていない配列を1回だけ探索する場合は、indexOf()で十分です。大きなソート済みデータを繰り返し探索する場合は、二分探索が適切なツールです。

まとめ

JavaScriptでの二分探索の実装は、ソート済み配列が必要という要件を理解すれば簡単です。デフォルトでは反復的バージョンを使用してください。よりクリーンで、コールスタックのオーバーヘッドを回避できます。コードの構造上メリットがある場合は再帰的バージョンを使用しますが、必ず再帰呼び出しにreturnを付けることを忘れないでください。そして、探索前に必ず適切な数値比較関数で配列がソートされていることを確認してください。

よくある質問

はい、文字列配列がアルファベット順にソートされていれば、二分探索は動作します。JavaScriptの比較演算子はデフォルトで辞書順の文字列比較を処理するため、同じアルゴリズムロジックが適用されます。デフォルトのsortメソッドを使用して配列をソートするだけで、すでに辞書順にソートされます。

JavaScript配列は柔軟に設計されており、混合型を保持できるため、組み込みの二分探索は実用的ではありません。二分探索にはソートされた均一な型のコレクションが必要だからです。Lodashのようなライブラリはこの目的のためにsortedIndexOfを提供していますが、バニラJavaScriptでは独自に実装する必要があります。

標準的な実装は一致する要素の1つのインデックスを返しますが、必ずしも最初または最後の出現位置とは限りません。重複値の最初または最後のインデックスが必要な場合は、一致が見つかった後も左または右半分の探索を続けるようにアルゴリズムを修正する必要があります。

どちらも同じO(log n)の時間計算量を持つため、実行速度はほぼ同じです。ただし、反復的バージョンは再帰関数呼び出しのオーバーヘッドを回避し、定数メモリを使用するため、実際にはわずかに効率的です。非常に深い再帰の場合、再帰的バージョンはスタックオーバーフローのリスクもあります。

Complete picture for complete understanding

Capture every clue your frontend is leaving so you can instantly get to the root cause of any issue with OpenReplay — the open-source session replay tool for developers. Self-host it in minutes, and have complete control over your customer data.

Check our GitHub repo and join the thousands of developers in our community.

OpenReplay

More articles from OpenReplay Blog