ソートと二分探索 — 半分ずつ捨てて O(log N) にする

この章のテーマは「候補を半分ずつ捨てる」です。ソートされた列では、真ん中を1回見るだけで半分の候補を捨てられる——この単純な事実がO(N)の探索をO(log N)に変えます。N = 10^9 でもたった30回。二分探索はそれほど強力です。

ソートは「前処理」である

コーディングテストにおけるソートの役割は、並べ替え自体が目的というより、後の処理を楽にする前処理です。

O(N log N)のソートを1回払うと、その後の探索や判定が一気に安くなる——「N ≤ 10^5 だからO(N log N)まで許される。まずソートしてみるか」という発想は、それだけで解ける問題を大量に生みます。

二分探索の基本形

問題: 昇順ソート済み配列に値Xが含まれるか判定せよ。

function binarySearch(sorted: number[], x: number): boolean {
  let left = 0;
  let right = sorted.length - 1;
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (sorted[mid] === x) return true;
    if (sorted[mid] < x) left = mid + 1;   // 左半分を捨てる
    else right = mid - 1;                  // 右半分を捨てる
  }
  return false;
}

学習者

二分探索って、書くたびに <= だっけ < だっけ、mid + 1 だっけ…って毎回不安になるんだよね。動いてるけど自信がない、みたいな。

その不安は全人類共通です（笑うところではなく本当に、二分探索は「概念は簡単、境界はバグの巣」で有名なんです）。そこで、境界で迷わない書き方を紹介します。

バグらせない書き方: 「ダメ/OK」の境界を挟み撃つ

発想を変えて、「値を探す」のではなく**「条件の境界を探す」**と考えます。通称「めぐる式二分探索」と呼ばれる型です。

• ng : 条件を満たさないと分かっている位置
• ok : 条件を満たすと分かっている位置
• 2つの距離が1になるまで挟み撃つ

// 「x以上が初めて現れる位置」（lowerBound）を求める
function lowerBound(sorted: number[], x: number): number {
  let ng = -1;                    // 「x以上でない」と確定している位置
  let ok = sorted.length;         // 「x以上である」と確定している位置（番兵）
  while (ok - ng > 1) {
    const mid = Math.floor((ng + ok) / 2);
    if (sorted[mid] >= x) ok = mid;
    else ng = mid;
  }
  return ok;
}

この型の利点は、初期値を「配列の外」に置くことで空配列や端のケースが自動的に正しく処理されること、そして条件式 sorted[mid] >= x を差し替えるだけであらゆる境界探索に使い回せることです。

lowerBound が1つあれば、頻出クエリが全部O(log N)で書けます。

lowerBound(a, x)                    // x以上の最初の位置
a.length - lowerBound(a, x)         // x以上の個数
lowerBound(a, x + 1) - lowerBound(a, x)   // ちょうどxの個数

「ソート済み配列で個数を数える」問題はこのイディオムの独壇場です。付録のスニペット集にも収録します。

応用: 答えで二分探索

ここからがこの章のハイライトです。二分探索は「配列の中」だけでなく、「答えの候補空間」に対しても使えます。

問題: N本の丸太がある。K人に同じ長さの丸太を1本ずつ切り出したい。切り出せる長さの最大値を求めよ。（N, K ≤ 10^5、長さ ≤ 10^9）

「最大の長さ」を直接計算するのは難しそうです。しかし、問題をひっくり返して判定問題にすると急に簡単になります。

「長さLで切り出すとして、K本作れるか？」→ 各丸太から Math.floor(log / L) 本取れる。合計がK以上ならYES。

この判定はO(N)で書けます。そして重要な性質——**Lを短くするほど作りやすい（単調性）**があります。「YES/NOの境界」を二分探索で挟み撃てばいい、というわけです。

function maxLength(logs: number[], k: number): number {
  const canCut = (len: number): boolean => {
    let total = 0;
    for (const log of logs) total += Math.floor(log / len);
    return total >= k;
  };
 
  let ok = 0;                     // 長さ0なら必ず作れる（番兵）
  let ng = 1e9 + 1;               // 上限超えは作れない
  while (ng - ok > 1) {
    const mid = Math.floor((ok + ng) / 2);
    if (canCut(mid)) ok = mid;
    else ng = mid;
  }
  return ok;
}

計算量はO(N log(答えの範囲)) ≈ 10^5 × 30。答えの候補が10^9個あっても平気です。

「〇〇の最大値/最小値を求めよ」で直接計算が難しく、「答えを1つ決めれば達成可能か判定できる」なら、答えで二分探索。AtCoderの水色前の壁と言われる技ですが、型はこれだけです。

ソート+αの頻出コンビ

二分探索以外にも、ソートを前処理にした定番コンビを押さえておきます。

// 区間スケジューリングの前処理: 終了時刻でソート（次章の貪欲法で活躍）
intervals.sort((a, b) => a[1] - b[1]);
 
// 座標圧縮: 値の大小関係だけ残して 0,1,2,... に付け替える
const sorted = [...new Set(values)].sort((a, b) => a - b);
const rank = new Map(sorted.map((v, i) => [v, i]));   // 値 → 順位

座標圧縮は「値は10^9まであるが種類はN個しかない」ときに、値を配列の添字として扱えるようにする変換です。lowerBoundとMap（第4章）の合わせ技で、上位問題の前処理によく登場します。

この章のパターンの見分け方

メンター

「答えで二分探索」に気づけるかは、判定問題を作る練習量で決まります。「答えをLと仮置きしたら、YES/NOは簡単に判定できないか？」——難しめの最大化・最小化問題を見たら、必ず一度この自問をする癖をつけましょう。

まとめ

• ソートはO(N log N)の前処理。境界・隣接・端の構造が生まれ、後の処理が安くなる
• 二分探索の境界バグは「ng/okの挟み撃ち」型で根絶する。初期値は配列の外（番兵）
• lowerBound 1つで「以上の位置・以上の個数・ちょうどの個数」がすべて書ける
• 答えで二分探索: 最大化/最小化を「Lで達成可能か」の判定問題に変換し、YES/NO境界を挟み撃つ。単調性が条件
• 座標圧縮 = ソート + 重複除去 + Mapで順位付け

次章は、ソートと相性抜群の解法——「毎回ベストを選び続ける」貪欲法です。使える条件と、使ってはいけない場面の見極めを学びます。