抽象化で理解する二分探索の本質 ~ 高階関数で「めぐる式」のさらに先へ ~

0. ごあいさつ

こんにちは、somnicattus と申します。TypeScript を使うソフトウェアエンジニアです。

二分探索アルゴリズムを高階関数で一般化した TypeScript ライブラリ "binary-search-generalized" を公開しました。

• GitHub: https://github.com/somnicattus/binary-search-generalized
• npm: https://www.npmjs.com/package/binary-search-generalized

このライブラリは、二分探索の一般化として知られる「めぐる式二分探索」を手がかりに、高階関数でさらに一般化した、汎用的な二分探索関数を提供するものです。

この記事では、二分探索アルゴリズムの理解と、高階関数によるコードの再利用方法を中心に、ライブラリを作りながら考えたことを記録しておきます。

この記事は以下のような読者を対象としています:

• 二分探索アルゴリズムを深く理解したい方
• 高階関数によるコードの再利用に興味のある方

1. 二分探索とは

二分探索 (binary search) は、探索範囲を半分ずつ狭めながら目的の値を見つける手法です。計算機科学を学ぶと最初の方に登場する印象深いアルゴリズムのひとつだと思います。

教材ではソート済み配列の検索でよく使われますが、二分探索の本質は配列の検索ではありません。
二分探索は、探索対象の数の集合のうち、範囲内で真偽が切り替わる境界値を 1 つだけ持つ条件に対して、その境界値を特定するアルゴリズムです。

このような抽象化は日本の競技プログラミング界隈では「めぐる式二分探索」として知られます。詳細な解説は以下の解説記事に委ねます。

https://qiita.com/drken/items/97e37dd6143e33a64c8c

ライブラリを作るにあたり、似たようなことを考えた先駆者がいないか探しましたが、「二分探索 高階関数」と検索してもそれらしいライブラリや技術記事は見当たりませんでした。

2. 二分探索の本質

二分探索の抽象化で重要なのは次の点です。

• 単調: 条件式 (predicate) は探索範囲内で単調変化し、1 点を境に常に真（always）の領域と常に偽（never）の領域に分けられること
• 収束: 探索範囲の二分点（midpoint）を算出でき、範囲を半分ずつ狭めていくと許容誤差 (epsilon) 以内に収束すること

binary-search-generalized では、この考え方を一般化してプログラムで再利用できるように、上記の各要素 (predicate, always, never, midpoint, epsilon)を引数として注入・再利用できる形式に整理しています。

3. 高階関数による一般化二分探索の実装

高階関数 (higher order function) とは、関数を引数に取ったり関数を返したりする関数のことです。
JavaScript/TypeScript では関数が第一級オブジェクトのため、条件式や二分点の取り方といった二分探索の「振る舞い」を引数として渡して差し替えられます。
高階関数についての詳細な解説は以下の MDN ドキュメントや解説記事に委ねます。

https://developer.mozilla.org/ja/docs/Glossary/First-class_Function

以下は、binary-search-generalized ライブラリのコアである binarySearch の実装 (一部省略・改変) です。

/** 単調（always/never）と収束（midpoint/epsilon）を注入できる一般化二分探索 */
export function binarySearch(
  alwaysEnd: number,
  neverEnd: number,
  predicate: (value: number) => boolean,
  midpoint: (always: number, never: number) => number,
  epsilon: number,
): number {
  // 現在の探索範囲を記録する変数
  let always = alwaysEnd;
  let never = neverEnd;

  // 探索区間の幅が epsilon 以内になるまで探索を続ける
  while (Math.abs(always - never) > epsilon) {
    // 二分点を算出し、これに対して条件式を検証する
    const mid = midpoint(always, never);
    // 検証結果に従って always と never いずれかを収束に近づけ、探索範囲を狭める
    if (predicate(mid)) always = mid;
    else never = mid;
  }

  // always 側の境界値を返す (never 側を返してもよいが、分かりやすさのため)
  return always;
}

以下に、この関数の抽象化の要素を解説します。

単調な条件とその範囲（predicate/always/never）

predicate は、探索対象となる条件式を与えます。
この条件は alwaysEnd と neverEnd で指定した範囲に唯一の境界値（常に真（always）の領域と常に偽（never）の領域を分ける点）を持つ条件である必要があります。
二分探索はこの条件式の境界値を探索するアルゴリズムです。

alwaysEnd と neverEnd は、条件 predicate に対して、それぞれ真あるいは偽となることが分かっている値です。この 2 値が探索範囲 [alwaysEnd, neverEnd) あるいは (neverEnd, alwaysEnd] を与えます。この範囲内で predicate の真偽が 1 回だけ切り替わります。

この抽象化によって、以下の例のように、任意の単調な条件と範囲に対して境界値を探索することができます。

• 10 < n <= 100 の範囲で n^2 >= 160 となる最小の整数 n を探す
• -π/2 <= x < π/2 の範囲で sin(x) <= 0.5 となる最大の数 x を探す
• ソートされた配列 arr のインデックスのうち要素の値が 10 以下である最大のインデックスを探す

収束と終了条件 (midpoint/epsilon)

midpoint は、探索範囲 always と never を二分する中央の値 mid を与えます。
mid を predicate で検証し、その結果によって always と never のどちらかを mid で置き換えることで範囲を狭めます。
この操作によって最終的に探索範囲を epsilon 以内に収束させる必要があります。通常は mid = (always + never) / 2 となります。

epsilon は許容誤差を与えます。二分探索が進んで always と never の探索範囲が epsilon より狭くなるまで収束すると、探索は終了します。整数であれば epsilon = 1 です。

この抽象化によって、任意の数値集合に対して二分探索を行うことができます。

• 整数を対象に探索する場合、midpoint は床関数などで常に整数になるようにし、epsilon = 1 に設定します。
• 偶数を対象に探索する場合、midpoint は常に偶数になるようにし、epsilon = 2 に設定します。
• 実数を対象に探索する場合、midpoint は単に相加平均をとり、epsilon に 5e-3 など欲しい精度を設定します。

4. 一般化二分探索の使用 (配列の探索)

一般化した関数を使って、配列の探索に当てはめると、以下のようになります。

• 探索対象の数の集合: ソートされた配列のインデックス
• 条件: あるインデックスに対する配列の要素の値が検索対象以下か、そうでないか
• 範囲内で真偽が切り替わる唯一の境界値: 検索対象以下の要素と検索対象より大きい要素が隣接するインデックス

注意すべきことは、配列の要素は探索対象ではなく、 array[i] <= target という条件式の一部 であるということです。あくまで検索対象はインデックスです。

昇順の配列に対する二分探索を関数の引数で表すと、以下のようになります。

引数	値	説明
predicate	(index) => arr[index] <= target	そのインデックスの配列の要素の値が検索対象以下である
alwaysEnd	-1	最初の要素が target より大きい可能性を考慮してインデックスの 1 つ外の値を指定[1]
neverEnd	arr.length	最後の要素が target 未満である可能性を考慮してインデックスの 1 つ外の値を指定[1:1]
midpoint	(always, never) => Math.floor((always + never) / 2)	常に整数を返す必要があるので床関数を適用
epsilon	1	相異なる整数の差の最小値

以上の条件を適用すると以下のようなコードになります。

const arr = [0, 1, 1, 2, 3, 5, 8, 13, 21];
const target = 10;

const maybeTargetIndex = binarySearch(
  -1,
  arr.length,
  (index) => arr[index] <= target,
  (always, never) => Math.floor((always + never) / 2),
  1,
);

console.log(maybeTargetIndex); // 6
console.log(arr[maybeTargetIndex]); // 8

5. 部分適用による特化

部分適用 (partial application) とは、複数引数の関数の一部に値を先に固定して、新しい関数を得る手法です。

例えば binarySearch() に対して midpoint = (a, n) => Math.floor((a + n) / 2) と epsilon = 1 を先に束縛しておくと、簡単に整数に特化した二分探索関数を作ることができます。

詳細な説明は以下の解説記事に委ねます。

https://www.okb-shelf.work/entry/partial_and_curry

以下は、部分適用によって配列に特化した関数を定義する例です（一部省略・改変）。

/** 二分探索による配列の探索 */
const binarySearchArray = <T extends number | bigint | string>(
  array: readonly T[],
  target: T
): number => {
  // 昇順・降順の差を吸収した条件
  const predicate = array[0] < array[array.length - 1]
    ? (index) => array[index] <= target
    : (index) => array[index] >= target;

  // 汎用的な二分探索に部分適用
  const index = binarySearch(
    -1,
    array.length,
    predicate,
    (always, never) => Math.floor((always + never) / 2),
    1,
  );
  
  // 見つからなければ -1 を返却
  if(index === -1 || array[index] !== target) return -1;
  return index;
}

// 使用例
const arr = ['apple', 'banana', 'cherry'];
const target = 'cherry';
const index = binarySearchArray(arr, target);

console.log(index); // 2

もとの binarySearch は引数があまりに多くて汎用的すぎますが、このように引数の部分適用によってある程度の汎用性を持った実用的な関数を定義することができます。

binary-search-generalized では、部分適用を使用して、整数、倍精度浮動小数点数、長整数、配列に対して特殊化した関数も提供しています。

6. さらなる一般化

二分探索はさらに一般化することが可能です。

大小関係を定義できる任意のデータに対する探索

比較関数 comparator を引数に取ることで、数値以外の任意のデータに対しても探索ができます。

binary-search-generalized でも実装されています。

多次元の条件式に対する探索

単調な変化軸を 2 つ以上もつ条件式に対して、矩形（長方形、直方体など）の範囲を指定して「境界線」や「境界面」を算出できます。

binary-search-generalized でも将来的に実装を検討しています。

7. まとめ

二分探索の本質は「単調な条件の境界を特定すること」です。predicate/always/never と midpoint/epsilon を言語化できれば、配列以外の課題に対しても同じ型の思考で解けます。

汎用的な高階関数で振る舞いを引数に逃がし、部分適用で実用的な特化関数を組み立てると、小さく作って広く使えます。

記事のコメント、ライブラリの PR/Issue を歓迎します。では、良い探索を (GPT-5 が考えた締めの挨拶)。

追伸: 一部の執筆作業を GPT5 に任せてみましたが、大部分は自分で執筆することになりました。最終的に自分の伝えたいことを言語化できるのは自分だけだな、と感じました。

参考リンク・引用

binary-search-generalized

• ライブラリ: https://www.npmjs.com/package/binary-search-generalized
• リポジトリ: https://github.com/somnicattus/binary-search-generalized

引用した記事・資料

• めぐる式二分探索: https://x.com/meguru_comp/status/697008509376835584
• Qiita: 二分探索の解説: https://qiita.com/drken/items/97e37dd6143e33a64c8c
• MDN: First-class function: https://developer.mozilla.org/ja/docs/Glossary/First-class_Function
• 部分適用の解説: https://www.okb-shelf.work/entry/partial_and_curry

脚注

1. 指定した 2 つの端点は決して評価対象にならないため、配列のインデックス外の値を指定しても問題ありません。