JavaScriptの探索アルゴリズム｜二分探索・線形探索の実装と計算量で選ぶ基準

配列から目的の要素を見つける処理は、書き方を変えるだけで必要な手数が数十万倍変わります。要素数1,000万の配列では、探索ループが回る回数は線形探索で最大1,000万回、二分探索で最大24回です。本記事で示す回数はすべて、比較演算子の実行回数ではなく探索ループの反復回数を指します。ただし二分探索は、配列が探索時の比較規則に従ってソートされていないと、正しい結果を保証できません。要素が存在していても、エラーを出さずに「見つからない」と返すことがあります。ここでは線形探索・二分探索・ハッシュ（Map）の3方式を、実装と計算量の両面から比較します。本文のコードと反復回数は node v26.5.0（macOS）で実行し、返り値まで確認しています。実行時間を示す箇所は測定条件を併記します。なお本記事が扱うのは配列を探すアルゴリズムであり、検索エンジンのランキングアルゴリズムやSNSの表示順アルゴリズムは対象外です。

まとめ：探索方式を選ぶ4つの判断

• 未ソートの配列から1回だけ探すなら線形探索。すでにソート済みなら、1回の検索でも二分探索を候補にします。indexOf・includes・find の標準メソッドで十分です。
• 同じ配列を何度も探し、ソート済みの状態を保てるなら二分探索。1,000万要素でも最大24回の反復で終わります。
• キーで引く用途（IDから対象を取り出す等）なら二分探索より Map・Set。ソートの前処理が要らず、要素数が増えても取り出しの手数が伸びにくくなります。
• 二分探索の前処理でソートするときは、必ず比較関数を渡す。比較関数なしの sort() は要素を文字列に変換して並べるため、数値配列は [1, 10, 100, 25, 9] のような順序になり、その配列に二分探索を当てると見つかりません。

以下では、各方式の前提条件と実装上の境界条件を説明します。

探索アルゴリズムの3方式と使い分けの基準

配列に対する探索は、前提条件によって選べる方式が変わります。前提を無視して速い方式を選ぶと、速いどころか誤動作します。

線形探索：先頭から順に照合するO(n)

線形探索（リニアサーチ、逐次探索）は先頭から1つずつ比較する方式です。並び順に前提を置かないため、未ソートの配列でもオブジェクトの配列でも使えます。計算量は最悪でO(n)、つまり要素数に比例します。

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

実務では自前で書くより標準メソッドを使う場面がほとんどです。ここで indexOf と includes の挙動差を押さえておく価値があります。[NaN].indexOf(NaN) は -1 を返し、[NaN].includes(NaN) は true を返します。差の出どころは仕様が指定する比較アルゴリズムで、indexOf は IsStrictlyEqual、includes は SameValueZero を使います。ECMA-262 の 23.1.3.16 には allowing it to detect NaN array elements と目的まで書かれています。一方、+0 と -0 はどちらの比較でも等しい扱いなので、[-0].indexOf(0) は 0 を返しました。NaN を含みうるデータで存在確認をするなら includes を選ぶことになります。

二分探索：ソート済み配列を半分ずつ捨てるO(log n)

二分探索（バイナリサーチ、2分探索法）は、ソート済みの配列の中央要素と目的の値を比較し、探索範囲を毎回半分に切り捨てる方式です。1回の比較で候補が半分になるため、計算量はO(log n)になります。要素数1,000万の配列で末尾の値を探したときの反復回数は24回でした。存在しない値や配列の各所を探しても24回を超えず、ceil(log2(n + 1)) と一致します。

掲載する実装は、NaNや空要素を含まない数値配列が昇順に並び、探索値も数値であることを前提にします。降順の配列やオブジェクト配列では、並べ替えと探索で同じ比較規則を使うよう実装を変更する必要があります。この前提が崩れたときにどう壊れるかは後述します。

ハッシュ探索：Map・Setによるキーからの直接参照

キーから格納位置を直接計算する方式をハッシュ法と呼びます。キーと値の対応でデータを持てるなら、そもそも配列を走査しない選択肢があります。Map の取り出しが速いのは実装任せの性質ではなく、ECMA-262 の 24.1「Map Objects」が on average, provide access times that are sublinear on the number of elements in the collection. と実装への要求を明記しているためです。仕様が要求するのは、平均アクセス時間が要素数に対して劣線形となることです。一定時間のO(1)や、ハッシュテーブルによる実装までは保証していません。実際の速度は実装とキーに依存します。node v26.5.0 で100万件の文字列キーを用意し末尾のキーを引いたところ、Array.prototype.indexOf は200回の平均で1回あたり9.5から10ミリ秒、Map.prototype.get は500万回の平均で1回あたり数十ナノ秒でした。Map.prototype.get 側を500万回回しているのは、1回が計測の分解能を下回るためです。同じキーを繰り返し引く形の測定はJITの最適化を受けやすく、実行のたびに数倍ぶれます。

探索がボトルネックになっている既存コードでは、アルゴリズムを二分探索に置き換えるより、データ構造を Map に変えるほうが改修コストも実行時間も小さく済むことが多くなります。

線形探索・二分探索・Mapの前提条件と計算量

判断の分かれ目は「探す回数」と「ソートを維持できるか」です。未ソートの配列を1回だけ探すためにO(n log n)のソートを追加するなら、線形探索のO(n)より計算量が増えます。すでにソート済みなら、この前処理は不要です。同じ配列を繰り返し探すなら、ソートのコストは初回だけなので二分探索が効いてきます。

二分探索のJavaScript実装

二分探索は、探索範囲の下端 lo と上端 hi を持ち、中央 mid の値を見て範囲を詰めていきます。実装は目的によって2種類を使い分けます。

binarySearchによる一致位置の取得

function binarySearch(arr, target) {
  let lo = 0;
  let hi = arr.length - 1;
  while (lo <= hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) {
      lo = mid + 1;
    } else {
      hi = mid - 1;
    }
  }
  return -1;
}

範囲の上端を arr.length - 1（最終要素の添字）にしたので、ループ継続条件は lo <= hi になります。範囲を詰めるときに mid + 1・mid - 1 と1つずらすのは、すでに比較済みの mid を次の範囲から外すためです。この「1つずらす」を落とすと無限ループになります。

値が重複する場合、この実装は一致した位置のいずれかを返し、先頭位置は保証しません。[1, 3, 3, 3, 5, 7] から3を探すと、この実装は添字2を返すのに対し、indexOf と次の lowerBound はどちらも先頭の添字1を返します。先頭位置が必要なら lowerBound を使います。

挿入位置を返すlowerBound

「この値以上が最初に現れる位置」を求める形も実務ではよく使います。ソート済み配列への挿入位置の決定や、範囲内の件数を数える用途がこれに当たります。

function lowerBound(arr, target) {
  let lo = 0;
  let hi = arr.length;
  while (lo < hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (arr[mid] < target) {
      lo = mid + 1;
    } else {
      hi = mid;
    }
  }
  return lo;
}

こちらは上端を arr.length（最終要素の1つ後ろ）に取るため、継続条件が lo < hi、hi の更新が mid - 1 ではなく mid になります。基本形と条件を混ぜると壊れるので、2つの型はセットで覚えるのが安全です。0, 2, 4, … と並ぶ1,000万要素の配列に対し lowerBound(arr, 7) は4を、lowerBound(arr, 20000000) は10000000（末尾の次）を返しました。

Array・TypedArrayの標準探索メソッドと二分探索の非対応

Array.prototype が持つ探索系メソッドは indexOf・lastIndexOf・includes・find・findIndex・findLast・findLastIndex の7つで、いずれも線形探索です。二分探索に相当するメソッドは Array.prototype にも Int32Array.prototype などのTypedArrayにもありません（node v26.5.0 で Object.getOwnPropertyNames を走査して確認）。ソート済み配列をO(log n)で引きたければ、上のような実装を自分で用意するか、その用途自体を Map に置き換えることになります。

二分探索が黙って壊れる2パターン

失敗しても例外が出ないため、壊れ方を知らないとテストで拾えません。

未ソート配列への二分探索による取りこぼし

ソートされていない [5, 1, 9, 3, 7] の5要素すべてを順に探すと、5と9は正しい添字0と2が返り、1・3・7は要素が存在するのに -1（見つからない）が返りました。中央要素との大小比較で「片側には無い」と判断して捨てるため、捨てた側に答えがあっても気づけません。当たるかどうかが配列の並びに左右される、つまり正しさが保証されない状態です。

配列を外部から受け取る関数で二分探索を使うなら、ソート済みであることを呼び出し側の責務として関数名やコメントで明示するか、開発時のみ検証を入れるのが現実的な対処です。

探索範囲の更新ミスによる無限ループ

// 壊れた実装：mid + 1 と mid - 1 の「1」を落としている
while (lo <= hi) {
  const mid = Math.floor((lo + hi) / 2);
  if (arr[mid] === target) return mid;
  if (arr[mid] < target) {
    lo = mid;
  } else {
    hi = mid;
  }
}

この形で [1, 3, 5, 7, 9] から存在しない値4を探すと、lo と hi が隣接したところで mid が同じ値に固定され、条件が永久に真のままになります。反復回数に上限を設けて実行したところ、50回を超えても終了しませんでした。存在しない値を探すテストケースを必ず入れておけば、この欠陥はすぐ表に出ます。

sort()の既定順序と二分探索の前処理の不一致

二分探索の前にソートをかける場面は多く、ここがもう1つの罠になります。

比較関数省略時のUTF-16コード単位による並び順

Array.prototype.sort に比較関数を渡さない場合、要素は文字列へ変換されたうえで比較されます。ECMA-262 の 23.1.3.30.2「CompareArrayElements」が Let xString be ? ToString(x). Let yString be ? ToString(y). と定め、その先の比較は 7.2.12「IsLessThan」の The comparison of Strings uses a simple lexicographic ordering on sequences of UTF-16 code unit values. に従います。数値配列でも例外ではありません。

const nums = [10, 9, 1, 100, 25];

nums.slice().sort();
// [1, 10, 100, 25, 9]  文字列として比較された結果

nums.slice().sort((a, b) => a - b);
// [1, 9, 10, 25, 100]  数値として比較された結果

前者の配列に対して先ほどの binarySearch で値9を探すと -1 が返り、後者なら添字1が返ります。ソートは成功しているように見え、二分探索も例外を投げないため、原因にたどり着くまでに時間を取られる種類の不具合です。通常の数値配列を数値の昇順に並べるときは、比較関数を明示して探索側の比較規則とそろえます。

安定ソートによる同値要素の相対順序の維持

比較関数が等しいと判定した要素どうしの相対順序が保たれる性質を安定ソートと呼びます。Array.prototype.sort の安定性は、ECMAScript 2019（ECMA-262第10版）の変更点として Other updates include requiring that Array.prototype.sort be a stable sort と挙げられ、現行仕様でも 23.1.3.30.1「SortIndexedProperties」に i.e., the sort is stable. と明記されています。V8の実装はES2019の公開より前で、2018年9月28日のV8公式ブログが Timsort is available starting with V8 v7.0 and Chrome 70. と告知し、2018年10月15日公開のV8 v7.0リリース記事に Array.prototype.sort is now stable in V8 v7.0. と書かれています。キー b・a・b・a・b の順に並んだオブジェクト配列をキーで並べ替えると、a同士・b同士の元の順序が維持された結果になります。

この保証があるため、「まず日付で並べ、次に優先度で並べる」といった多段ソートを安全に書けます。後段で優先度を比較した結果が同じになる要素どうしでは、前段で付けた日付順が維持されます。優先度が異なる要素間の順序は、後段のソートによって変わります。

元の配列を壊さないtoSorted

sort は対象の配列を破壊的に並べ替えます。元の配列を残したい場合、以前は slice() でコピーしてからソートする必要がありましたが、toSorted が新しい配列を返します。MDNのBaselineは「広く利用可能」で、2023年7月以降の主要ブラウザで使えます。[3, 1, 2].toSorted() を実行しても元の配列は [3, 1, 2] のままでした。ただし toSorted も比較関数を省けば文字列比較になる点は sort と同じです。

他言語の「(lo + hi) >>> 1」をJavaScriptへ持ち込むべきでない理由

二分探索の解説記事では、中央の添字を Math.floor((lo + hi) / 2) ではなく (lo + hi) >>> 1 と書く例をよく見かけます。これはJavaで、非負の添字の和が符号付き32ビット整数の上限を超える問題への対策としてJoshua Blochが2006年に紹介した書き方です。C言語には >>> 演算子がなく、符号なし整数への変換と右シフトなどを使います。JavaScriptに持ち込む理由はありません。それどころか、JavaScriptでは >>> のほうが先に壊れます。

JavaScriptの数値は倍精度浮動小数点数で、整数として正確に扱える上限は Number.MAX_SAFE_INTEGER の 9,007,199,254,740,991 です（ECMA-262 21.1.2.6 に The value of Number.MAX_SAFE_INTEGER is 9007199254740991 と定義されています）。一方、配列の length が取りうる最大値は 4,294,967,295（2の32乗から1を引いた値）です。ECMA-262 10.4.2.2「ArrayCreate」に If length > 2^32 - 1, throw a RangeError exception. とあり、実際に 2の32乗 を length へ代入すると RangeError: Invalid array length になりました。つまり lo + hi は最大でも約85億9,000万にしかならず、安全整数の上限より6桁小さい値です。Math.floor((lo + hi) / 2) が桁あふれする余地はありません。

ところが >>> 演算子はオペランドを符号なし32ビット整数へ変換します。配列長の上限付近を入れて確かめると、この変換で値が失われます。

const lo = 4294967294;
const hi = 4294967294;

lo + hi;                       // 8589934588（Number.isSafeInteger は true）
(lo + hi) >>> 1;               // 2147483646  32ビットへ丸められて誤った中央値
Math.floor((lo + hi) / 2);     // 4294967294  正しい中央値

現実のブラウザやNode.jsで40億要素の配列を確保することはまずないため、この差が本番で表面化する可能性は低いままです。それでも、他言語の桁あふれ対策としてコピーしてきた書き方が、JavaScriptでは桁あふれの唯一の原因になっているという構図は把握しておくべきです。JavaScriptで二分探索を書くなら Math.floor((lo + hi) / 2) で十分であり、ビット演算に置き換える動機はありません。

ビッグO記法の読み方と、実測で確かめる手順

ビッグO記法（O記法、オーダー記法）は、入力サイズが増えたときに処理量がどう伸びるかを表す表記です。定数倍や低次の項を切り捨て、伸び方の形だけを残します。

1,000万要素での線形探索と二分探索の反復回数

0, 2, 4, … と並ぶ要素数1,000万の配列で、末尾の値と、存在しない値の2種類を探したときの反復回数は次のとおりです。

反復回数は実行環境に依存しない決定的な値です。同じ比較を壁時計時間へ置き換えると、二分探索の24回は1回の計測が分解能を下回るため、同じコードを測り直すだけで倍率が1桁変わりました。伸び方の差を示すには、実行時間より反復回数のほうが再現できます。

O記法に現れない定数倍と実行時間への影響

ビッグO記法が切り捨てた定数倍は、要素数が小さいうちは順位を逆転させます。同じ探索を200万回繰り返して末尾の要素を探すと、16要素の配列では線形探索が約60ミリ秒、二分探索が約145ミリ秒で線形探索のほうが速く、128要素では線形探索が約390ミリ秒、二分探索が約240ミリ秒と順位が入れ替わりました。個々のミリ秒は測り直すと1割前後ぶれ、逆転する要素数も実行環境で変わるので、この数字自体を判断基準には使えません。O記法は「どちらが速いか」ではなく「要素数が増えたときどちらが先に破綻するか」を示す道具です。

実測でアルゴリズムを比較するときは、JITコンパイルの最適化や測定順序の影響で結果が大きく変わります。測り方そのものの注意点はマイクロベンチマークとは何か？基本概念と重要性を徹底解説、メリット・デメリットや活用例も紹介で扱っています。

用途別に見るアルゴリズムとデータ構造の対応

アルゴリズムの種類は、扱うデータ構造とセットで決まります。配列探索以外の問題については、対応するデータ構造と解説記事を以下に示します。

処理順の制御はスタックとキューの違い｜FIFO・LIFOと使い分け・Python実装を図解、つながりをたどる探索はグラフ理論とは？頂点と辺の基礎から最短経路・グラフDB・GNNの実装応用までが対応します。自分を呼び出す形で書く再帰の仕組みとスタックの制約は再帰関数とは？自分を呼ぶ関数の仕組みとスタック・末尾再帰・実務判断を解説に、メモ化で計算量を落とす具体例はPythonでフィボナッチ数列を再帰関数で実装する方法｜計算量とメモ化・反復での高速化にまとめてあります。完全一致ではなく類似度で候補を返す探索は近似最近傍探索とは？HNSW・IVF・PQの選び分けとRecall調整を実装目線で解説【2026年版】が扱います。

よくある質問

二分探索とはどういう意味ですか？

ソート済みのデータの中央と目的の値を比べ、目的の値が無いほうの半分を毎回切り捨てていく探索方式です。1回の比較で候補が半分になるため、要素数1,000万でも24回の反復で答えが確定します。バイナリサーチ、2分探索法とも呼ばれます。

2分探索法の計算量は？

最悪計算量はO(log n)です。対数の底は2で、要素数が2倍になっても反復は1回しか増えません。要素数1,000万に対する log2(10,000,000) は約23.25で、実測した最大反復回数24回と一致します。空間計算量は、反復で書けばO(1)、再帰で書けば呼び出し段数ぶんのO(log n)です。

線形探索と二分探索の違いは何ですか？

前提条件と計算量が違います。線形探索は並び順に前提を置かず先頭から順に照合するO(n)、二分探索はソート済みであることを前提に範囲を半分ずつ捨てるO(log n)です。1,000万要素での反復回数は最大1,000万回と24回でした。未ソートの配列に二分探索を当てると、要素が存在していても見つからないと返すことがあり、正しい結果を保証できません。

2分探索の範囲はどう管理しますか？

下端 lo と上端 hi の2変数で管理します。上端を最終要素の添字（arr.length - 1）に取る形ではループ条件が lo <= hi、範囲の更新が mid + 1・mid - 1 になります。上端を最終要素の1つ後ろ（arr.length）に取る形ではループ条件が lo < hi、更新が mid + 1・mid になります。2つの型の条件を混ぜると無限ループや取りこぼしが起きます。

JavaScriptに二分探索の標準メソッドはありますか？

ありません。Array.prototype の探索系メソッドは7つありますが、すべて線形探索です。TypedArrayにも二分探索のメソッドはありません。O(log n)で引きたい場合は自前で実装するか、用途ごと Map に置き換えます。

関連記事

• スタックとキューの違い｜FIFO・LIFOと使い分け・Python実装を図解
• 再帰関数とは？自分を呼ぶ関数の仕組みとスタック・末尾再帰・実務判断を解説
• グラフ理論とは？頂点と辺の基礎から最短経路・グラフDB・GNNの実装応用まで
• Pythonでフィボナッチ数列を再帰関数で実装する方法｜計算量とメモ化・反復での高速化
• 近似最近傍探索とは？HNSW・IVF・PQの選び分けとRecall調整を実装目線で解説【2026年版】