--- title: "二分探索のJavaScript実装｜線形探索との違い・計算量・境界の求め方" url: "https://www.issoh.co.jp/tech/details/4867/" published: 2025-01-16 updated: 2026-11-04 categories: ["JavaScript"] publisher: "株式会社一創" --- # 二分探索のJavaScript実装｜線形探索との違い・計算量・境界の求め方 配列から目的の要素を見つける処理は、書き方を変えるだけで必要な手数が数十万倍変わります。要素数1,000万の配列では、探索ループが回る回数は線形探索で最大1,000万回、二分探索で最大24回です。本記事で示す回数はすべて、比較演算子の実行回数ではなく探索ループの反復回数を指します。ただし二分探索は、配列が探索時の比較規則に従ってソートされていないと、正しい結果を保証できません。要素が存在していても、エラーを出さずに「見つからない」と返すことがあります。ここでは線形探索・二分探索・ハッシュ（Map）の3方式を実装と計算量の両面から比較し、二分探索については重複要素の先頭位置・末尾の次の位置を返す `lowerBound`・`upperBound`、配列を使わない「答えの二分探索」、他言語の標準ライブラリとの返り値の違いまで扱います。本文のコードと反復回数は node v26.5.0（macOS）で実行し、返り値まで確認しています。実行時間を示す箇所は測定条件を併記します。なお本記事が扱うのは配列を探すアルゴリズムであり、検索エンジンのランキングアルゴリズムやSNSの表示順アルゴリズムは対象外です。 ## まとめ：探索方式と二分探索の型を選ぶ判断 - すでにソート済みなら、1回の検索でも二分探索を候補にします。未ソートの配列から1回だけ探すなら線形探索を選びます。`indexOf`・`includes`・`find` の標準メソッドで十分です。 - 同じ配列を何度も探し、ソート済みの状態を保てるなら二分探索。1,000万要素でも最大24回の反復で終わります。 - キーで引く用途（IDから対象を取り出す等）なら二分探索より `Map`・`Set`。ソートの前処理が要らず、要素数が増えても取り出しの手数が伸びにくくなります。 - 重複を含む配列で先頭位置や個数が要るなら、一致位置を返す基本形ではなく `lowerBound`・`upperBound` を使う。2つの差がその値の個数になります。 - 通常の数値配列を数値の昇順に並べて二分探索する場合は、ソートに数値用の比較関数を渡す。比較関数なしの `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](https://tc39.es/ecma262/multipage/indexed-collections.html#sec-array.prototype.includes) には `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や空要素を含まない数値配列が昇順に並び、探索値もNaN以外の数値であることを前提にします。降順の配列やオブジェクト配列では、並べ替えと探索で同じ比較規則を使うよう実装を変更する必要があります。この前提が崩れたときにどう壊れるかは後述します。 ### ハッシュ探索：Map・Setによるキーからの直接参照 キーから格納位置を直接計算する方式をハッシュ法と呼びます。キーと値の対応でデータを持てるなら、そもそも配列を走査しない選択肢があります。`Map` の取り出しが速いのは実装任せの性質ではなく、[ECMA-262 の 24.1「Map Objects」](https://tc39.es/ecma262/multipage/keyed-collections.html#sec-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` は1回あたり7.7から10ミリ秒（200回の平均・測定日による幅）、`Map.prototype.get` は十数から数十ナノ秒（500万回の平均）でした。同じキーを繰り返し引く測定はJITの最適化を受けやすく、後者は実行のたびに数倍ぶれます。 探索がボトルネックになっている既存コードでは、同じキーの完全一致検索を繰り返し、追加メモリを許容できるなら、データ構造を `Map` に変える案を、二分探索への置き換えより先に検討します。範囲検索や「この値以上の最初の要素」が要るなら `Map` では答えられないので、ソート済み配列と二分探索が残ります。配列の全件走査が業務システムの複数の画面や処理に散らばり、データの持ち方から設計し直す必要がある場合は、[フルスクラッチ開発](/service/system/fullscratch/)で作り直すほうが早いこともあります。 ### 線形探索・二分探索・Mapの前提条件と計算量 | 方式 | 前提 | 計算量 | 1,000万要素での反復回数 | JSの標準API | | ------ | ------ | ----------- | -------------- | ------------------------- | | 線形探索 | なし | O(n) | 最大10,000,000 | indexOf / includes / find | | 二分探索 | ソート済み | O(log n) | 24 | なし（自前実装） | | ハッシュ探索 | キーを持てる | 平均で劣線形（仕様上） | 実装・キーに依存 | Map.get / Set.has | 判断の分かれ目は「探す回数」と「ソートを維持できるか」です。未ソートの配列を1回だけ探すためにO(n log n)のソートを追加するなら、線形探索のO(n)より計算量が増えます。すでにソート済みなら、この前処理は不要です。同じ配列を繰り返し探すなら、ソートのコストは初回だけなので二分探索が効いてきます。データベースでこの「並べた状態を保って範囲を絞る」役を担うのがインデックスで、列の並び順が探索の効き方を左右する点は[複合インデックスとは？列の順番で効き方が変わる理由とEXPLAINでの確認手順](/tech/details/18984/)で扱っています。 ## 二分探索の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` を使います。 ### 13要素の配列で見るlo・hi・midの推移 上の `binarySearch` に各反復の変数を出力する1行を足し、`[3, 8, 12, 19, 23, 31, 40, 47, 55, 62, 70, 84, 91]`（13要素）から47と20を探しました。47は添字7にあり、20は配列に存在しません。 | 探す値 | 反復 | lo | hi | mid | arr\[mid\] | 次の動き | | --- | -- | -- | -- | --- | ---------- | ------------------ | | 47 | 1 | 0 | 12 | 6 | 40 | 40 < 47 なので lo = 7 | | 47 | 2 | 7 | 12 | 9 | 62 | 62 > 47 なので hi = 8 | | 47 | 3 | 7 | 8 | 7 | 47 | 一致・添字7を返す | | 20 | 1 | 0 | 12 | 6 | 40 | 40 > 20 なので hi = 5 | | 20 | 2 | 0 | 5 | 2 | 12 | 12 < 20 なので lo = 3 | | 20 | 3 | 3 | 5 | 4 | 23 | 23 > 20 なので hi = 3 | | 20 | 4 | 3 | 3 | 3 | 19 | 19 < 20 なので lo = 4 | 20を探した側は、4回目のあとに lo=4・hi=3 となって `lo <= hi` が偽になり、-1 を返して終わります。13要素での最大反復回数は ceil(log2(14)) の4回で、存在しない値でもこれを超えません。終了時の `lo`（4）は、20を挿入すれば昇順が保たれる位置と一致します。この性質を返り値として取り出したのが次の `lowerBound` です。 ### 重複要素の先頭位置と末尾の次の位置を返すlowerBound・upperBound 「この値以上が最初に現れる位置」を求める形も実務ではよく使います。ソート済み配列への挿入位置の決定や、範囲内の件数を数える用途がこれに当たります。 ``` 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（末尾の次）を返しました。 比較の `<` を `<=` に変えると、「この値より大きい要素が最初に現れる位置」を返す `upperBound` になります。2つの差が、その値の個数です。 ``` function upperBound(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; } const d = [1, 3, 3, 3, 5, 7]; lowerBound(d, 3); // 1 upperBound(d, 3); // 4 upperBound(d, 3) - lowerBound(d, 3); // 3（3の個数） upperBound(d, 4) - lowerBound(d, 4); // 0（4は無い） upperBound(d, 6) - lowerBound(d, 3); // 4（3以上6以下の件数） ``` 値の個数や「3以上6以下」のような範囲の件数が、線形に数えずO(log n)で求まります。日時でソートしたログから期間内の件数を出す処理は、この2関数の組み合わせで書けます。 ### 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` に置き換えることになります。 ### Python・Java・C++・Go・Rustの標準二分探索と返り値の違い JavaScriptから他言語へ移植するとき、または他言語のコードを読むときに引っかかるのが、見つからなかったときと重複があるときの返り値です。同じ `[1, 3, 3, 3, 5, 7]` で3と4を探した結果を、各言語の処理系で実行して並べました（Python 3.9.6・Java 25.0.4.1・Apple clang 21・Go 1.27.2・Rust 1.99.1）。C++の `std::lower_bound` は添字ではなくイテレータを返すため、表には先頭からの距離を載せています。[cppreference](https://en.cppreference.com/cpp/algorithm/lower%5Fbound)の説明は `Iterator to the first element which is not ordered before value, or last if no such element is found.` で、対象値以上の要素が1つも無いときに末尾の `last` が返ります。 | 言語・関数 | 3を探す | 4を探す（無い） | 見つからないときの表現 | | -------------------------- | ------- | -------- | ------------ | | Python `bisect_left` | 1 | 4 | 挿入位置そのもの | | Python `bisect_right` | 4 | 4 | 挿入位置そのもの | | Java `Arrays.binarySearch` | 2 | \-5 | \-(挿入位置) – 1 | | C++ `std::lower_bound` | 1 | 4 | 挿入位置を指すイテレータ | | C++ `std::binary_search` | true | false | 真偽値のみ | | Go `slices.BinarySearch` | 1, true | 4, false | 位置と存在フラグの組 | | Rust `binary_search` | Ok(3) | Err(4) | Err(挿入位置) | | 本記事の `binarySearch` | 2 | \-1 | \-1 固定 | 重複のある3に対して、返る添字が1・2・3とばらけている点に注意が要ります。[Javaの Arrays.binarySearch](https://docs.oracle.com/en/java/javase/25/docs/api/java.base/java/util/Arrays.html#binarySearch%28int[],int%29)は `there is no guarantee which one will be found.` と明記し、[Rustの binary\_search](https://doc.rust-lang.org/std/primitive.slice.html#method.binary%5Fsearch)も `any one of the matches could be returned.` としています。先頭を保証するのはPythonの `bisect_left`、C++の `std::lower_bound`、[Goの slices.BinarySearch](https://pkg.go.dev/slices#BinarySearch)（Go 1.21で追加された `slices` パッケージの関数で、`returns the earliest position where target is found` と説明されています）で、本記事の `lowerBound` と同じ値を返します。[Pythonのbisect](https://docs.python.org/3/library/bisect.html)は3.10で `key` 引数が加わり、オブジェクトの配列も属性で引けるようになりました。 Javaの負の返り値は `-(r + 1)` で挿入位置に戻せます（-5なら4）。JavaScriptの `indexOf` の感覚で「-1なら見つからない」と判定すると、-5のような値を見つかった添字として扱ってしまいます。Javaでは `r < 0` で判定します。移植するときは、重複時にどの位置が必要か、見つからないときに挿入位置が要るかの2点を先に決めてから関数を選びます。 ## 配列が無くても使える「答えの二分探索」 二分探索が探せるのは配列の中身だけではありません。「値xで条件を満たすか」という判定が、xを大きくするとある境目から先ですべて真になる（単調である）なら、その境目を二分探索で求められます。配列の添字の代わりに答えの候補の範囲を半分ずつ捨てていく使い方です。最適値を直接計算しにくい問題でも、「この値で足りるか」の判定さえ書ければ答えが求まります。 ### ok・ngの2変数で境界を挟む書き方 重さ `[1, 2, 3, ..., 10]` の荷物を順番どおりに5日以内で運ぶとき、1日に積める最小の容量を求める例です。容量が大きいほど運びやすくなるので、「容量capで5日以内に運べるか」は単調な判定になります。 ``` function minCapacity(weights, days) { const canShip = (cap) => { let used = 1; let load = 0; for (const w of weights) { if (w > cap) return false; if (load + w > cap) { used++; load = 0; } load += w; } return used <= days; }; let ng = 0; // この容量では運べない let ok = weights.reduce((s, w) => s + w, 0); // 全部を1日で運べる容量 while (ok - ng > 1) { const mid = Math.floor((ok + ng) / 2); if (canShip(mid)) ok = mid; else ng = mid; } return ok; } minCapacity([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 5); // 15 ``` 重さと日数は正の整数、重さの合計は安全整数の範囲に収まるものとします。答えは15で、容量を1から順に試す全探索の結果とも一致しました。判定 `canShip` を呼んだのは6回です。`ng` は「必ず偽になる値」、`ok` は「必ず真になる値」で初期化し、差が1になるまで中央で判定して片方を動かします。終了時には `ng` と `ok` が隣り合い、`ok` が条件を満たす最小値になります。 この書き方は、前章の `lo <= hi` 型・`lo < hi` 型のどちらとも違い、境界の±1で迷う箇所がありません。初期値が「必ず偽」「必ず真」であることに加え、判定の単調性、整数の探索範囲、計算が安全整数の範囲に収まることを確認します。逆に、判定が単調でない問題（容量を増やすと一度通ったのにまた通らなくなる、など）にこの手法を当てると、誤った境界を返しても例外は出ません。適用前に単調性を言葉で説明できるかを確認します。 同じ考え方は開発ツールにも組み込まれています。[git bisect の公式リファレンス](https://git-scm.com/docs/git-bisect)は冒頭で `Use binary search to find the commit that introduced a bug` と説明しており、「このコミットでは不具合が出るか」という判定でコミット履歴を半分ずつ絞り込みます。正常なコミットと不具合のあるコミットが ng・ok の初期値に当たります。この型を練習問題で身につけたい場合、AtCoderの始め方は[AtCoderとは？色の目安と人数割合・難易度・コンテストの種類と始め方【2026年版】](/column/details/3596/)にまとめています。 ## 二分探索が黙って壊れる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」](https://tc39.es/ecma262/multipage/indexed-collections.html#sec-comparearrayelements)が `Let xString be ? ToString(x). Let yString be ? ToString(y).` と定め、その先の比較は [7.2.12「IsLessThan」](https://tc39.es/ecma262/multipage/abstract-operations.html#sec-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で安定ソートが必須になり、現行仕様の 23.1.3.30.1「SortIndexedProperties」にも `i.e., the sort is stable.` とあります。V8は仕様より先に対応しており、[V8公式ブログ（2018年9月28日）](https://v8.dev/blog/array-sort)は `Timsort is available starting with V8 v7.0 and Chrome 70.` と告知しています。 この保証があるため、「まず日付で並べ、次に優先度で並べる」多段ソートでは、優先度が同じ要素どうしの日付順が維持されます。二分探索の比較規則を「優先度、同じなら日付」にするなら、ソートも同じ2段の規則でそろえます。 ### 元の配列を壊さないtoSorted `sort` は対象の配列を破壊的に並べ替えます。元の配列を残すには `slice()` やスプレッド構文でコピーしてからソートする方法があり、`toSorted` を使えば1回の呼び出しで並べ替えた新しい配列が返ります。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年に紹介した](https://research.google/blog/extra-extra-read-all-about-it-nearly-all-binary-searches-and-mergesorts-are-broken/)書き方です。C言語には `>>>` 演算子がなく、符号なし整数への変換と右シフトなどを使います。JavaScriptに持ち込む理由はありません。それどころか、JavaScriptでは `>>>` のほうが先に壊れます。 JavaScriptの数値は倍精度浮動小数点数で、整数として正確に扱える上限は `Number.MAX_SAFE_INTEGER` の 9,007,199,254,740,991 です（[ECMA-262 21.1.2.6](https://tc39.es/ecma262/multipage/numbers-and-dates.html#sec-number.max%5Fsafe%5Finteger) に `The value of Number.MAX_SAFE_INTEGER is 9007199254740991` と定義されています）。一方、配列の `length` が取りうる最大値は 4,294,967,295（2の32乗から1を引いた値）です。[ECMA-262 10.4.2.2「ArrayCreate」](https://tc39.es/ecma262/multipage/ordinary-and-exotic-objects-behaviours.html#sec-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種類を探したときの反復回数は次のとおりです。 | 探す値 | 線形探索の反復回数 | 二分探索の反復回数 | | ------------------ | ---------- | --------- | | 末尾の要素（19,999,998） | 10,000,000 | 24 | | 存在しない値（19,999,997） | 10,000,000 | 24 | 反復回数は実行環境に依存しない決定的な値です。同じ比較を壁時計時間へ置き換えると、二分探索のように処理時間が短い測定では、同じコードを測り直すだけで倍率が1桁変わりました。伸び方の差を示すには、実行時間より反復回数のほうが再現できます。 ### O記法に現れない定数倍と実行時間への影響 ビッグO記法が切り捨てた定数倍は、要素数が小さいうちは順位を逆転させます。本記事の `linearSearch` と `binarySearch` をそのまま使い、末尾の要素を探す処理を200万回ずつ実行しました（Node.js v26.5.0、macOS、Intel Core i9-9880H。ウォームアップ後、実行順を交互に変えて各方式を5回測定し、その中央値を使用。この測定一式を2回実施）。16要素では線形探索が約57ミリ秒、二分探索が約139から150ミリ秒で線形探索のほうが速く、64要素でも線形探索が約149から163ミリ秒、二分探索が約212ミリ秒でした。128要素で線形探索が約265から277ミリ秒、二分探索が約252から254ミリ秒となり、ここでようやく順位が入れ替わります。逆転する要素数は実行環境で変わるので、この数字自体を判断基準には使えません。O記法は、要素数が増えたときの処理量の増え方を比較する道具です。具体的な実行時間や、許容時間を超える要素数は実測で確認します。 実測でアルゴリズムを比較するときは、JITコンパイルの最適化や測定順序の影響で結果が大きく変わります。測り方そのものの注意点は[マイクロベンチマークとは？正しい測り方と落とし穴をJMH・Goの実測で解説](/tech/details/8711/)で扱っています。 ### 内挿探索を選ぶ条件と避ける条件 二分探索の変種として教科書によく載るのが内挿探索です。中央ではなく、値の大きさから目的の値がありそうな位置を比例計算で予測して調べます。[Perl・Itai・Avniの1978年の論文](https://csaws.cs.technion.ac.il/~itai/publications/Algorithms/p550-perl.pdf)は、キーが一様に分布している（`assuming that the N keys are uniformly distributed.`）という前提で平均のアクセス回数がO(log log n)になることを示す一方、`In the worst case, interpolation search might require N accesses.` とも書いています。最悪は線形探索と同じO(n)です。 連番に近いID列や均等な間隔のタイムスタンプでは探索回数を減らせる可能性がありますが、値が偏った実データ（一部の値に集中する金額、指数的に増えるファイルサイズなど）では二分探索より遅くなりえます。分布を確かめないまま置き換える理由はなく、JavaScriptで配列を探すなら二分探索のままで十分です。 ## よくある質問 ### 二分探索とはどういう意味ですか？ ソート済みのデータの中央と目的の値を比べ、目的の値が無いほうの半分を毎回切り捨てていく探索方式です。1回の比較で候補が半分になるため、要素数1,000万でも24回の反復で答えが確定します。バイナリサーチ、2分探索法とも呼ばれます。 ### 2分探索法の計算量は？ 最悪計算量はO(log n)です。対数の底は2で、要素数が2倍になっても反復は1回しか増えません。掲載実装の最大反復回数は ceil(log2(n + 1)) で、要素数1,000万では24回となり、実行結果と一致します。空間計算量は、反復で書けばO(1)、再帰で書けば呼び出し段数ぶんのO(log n)です。 ### 線形探索と二分探索の違いは何ですか？ 前提条件と計算量が違います。線形探索は並び順に前提を置かず先頭から順に照合するO(n)、二分探索はソート済みであることを前提に範囲を半分ずつ捨てるO(log n)です。1,000万要素での反復回数は最大1,000万回と24回でした。未ソートの配列に二分探索を当てると、要素が存在していても見つからないと返すことがあり、正しい結果を保証できません。 ### 二分探索のやり方は？ データを昇順に並べたうえで、(1) 探索範囲の中央の要素を取り出す、(2) 目的の値と比べる、(3) 一致すれば終了し、目的の値のほうが大きければ中央より左側を、小さければ右側を範囲から外す、(4) 範囲が空になるまで繰り返す、の4手順です。範囲は下端 `lo` と上端 `hi` の2変数で持ち、上端を最終要素の添字に取るなら継続条件は `lo <= hi`、更新は `mid + 1`・`mid - 1` です。13要素の配列から47を探した例では3回で見つかりました。 ### JavaScriptに二分探索の標準メソッドはありますか？ ありません。`Array.prototype` の探索系メソッドは7つありますが、すべて線形探索です。TypedArrayにも二分探索のメソッドはありません。O(log n)で引きたい場合は自前で実装するか、用途ごと `Map` に置き換えます。 ## 関連記事 - [スタックとキューの違い｜FIFO・LIFOの意味と言語別の実装・落とし穴](/tech/details/4587/) - [再帰関数とは？自分を呼ぶ関数の仕組みとスタック・末尾再帰・実務判断を解説](/tech/details/15264/) - [グラフ理論とは？頂点と辺の基礎から最短経路・グラフDB・GNNの実装応用まで](/tech/details/15215/) - [Pythonでフィボナッチ数列を再帰関数で実装する方法｜メモ化・O(log n)](/tech/details/2755/) - [近似最近傍探索とは？HNSW・IVF・PQの選び分けとRecall調整を実装目線](/tech/details/16466/) --- 出典: [二分探索のJavaScript実装｜線形探索との違い・計算量・境界の求め方]()（株式会社一創）