線形探索と二分探索 — 1回引くだけなら並べると損

線形探索と二分探索。一列のデータカードと範囲を絞る仕切り、虫眼鏡と時計。

1回引くだけなら、並べ替えたほうが損になります。線形探索と二分探索を実測して、切り替わる点を見つけます。

前回: ソートアルゴリズム6種 — 並べ替えたら10が2の前に来た

これは【深掘り】の記事です。本線の順路ではありません。 このシリーズは言葉を覚える回にしません。 全部、手元で書いて、走らせて、数字を出します。 飛ばしても本線は進めます。

この記事のコマンドは、VMの中(Ubuntu Server)で打ちます。 Windows の PowerShell ではありません。VM の立て方は VMを29台溜めた話 — Ubuntu Serverの立て方 にあります。


「探すなら二分探索。線形探索は遅い」 と覚えていました。

それで、10万件の配列に対する検索が遅かったとき、こう直しました。

const sorted = [...items].sort((a, b) => a.id - b.id);
const found = binarySearch(sorted, targetId);

遅くなりました。

理由は、いま書けば当たり前です。この関数は1回呼ばれるたびに、10万件を並べ直していたからです。

並べる時間が、探す時間より圧倒的に大きい。

「二分探索は速い」は、並べ終わったあとの話です。 そこを勘定に入れていませんでした。

この記事では、「何回引くなら並べる価値があるのか」を、交差点が出るまで実際に測ります。

対象レベル: 中級〜上級 / 区分: 発展

目次

この記事でわかること

  • 線形探索の最大の強みは速さではなく、「並んでいなくても使える」こと
  • 1回しか引かないなら、線形探索のほうが速い。 ソートの O(n log n) を回収できない
  • 何回引いたら並べるべきかには、実測で求まる交差点があること
  • 二分探索の実装で必ず踏む3つの間違い(境界・Math.floor 忘れ・見つからないときの戻り値)
  • 実務で本当に欲しいのは「見つかったか」ではなく「どこに入れるか」(lower_bound)であることが多い
  • 順序が要らないならハッシュ、範囲検索が要るなら二分探索という一本の軸
  • 総当たりは「思いつかないときの敗北」ではなく、正しい道具であること

この記事でやること

  1. 実験用フォルダ ~/cslab/search を作り、この記事の作業を全部そこに閉じ込める
  2. 線形探索を書いて、最良・平均・最悪が本当に違うことを実測する
  3. 二分探索を書いて、100万件が何回で届くかを数えて確かめる
  4. わざと3つ間違えて、症状を見てから直す
  5. ソートの時間を含めて、線形と二分の交差点を実測で探す
  6. includes / Set / sort+二分探索を同じデータで比べる
  7. 総当たりが破綻する規模を実測し、正解データ作りに使うやり方をやってみる

先に知る言葉

この記事で初めて出てくる言葉です。 基本的な言葉は用語集にもまとめてあります。

言葉意味
線形探索前から順に1つずつ見る。並んでいなくてよい
二分探索真ん中を見て、半分を捨てる。並んでいることが前提
前処理探す前に1回だけやる準備(ここではソート)。回数で割って考える
交差点2つのやり方の合計時間が入れ替わる回数。ここより多く引くなら準備する価値がある
lower_boundその値以上が最初に現れる位置を返す探索。見つからなくても「入れるべき場所」が返る
半開区間[lo, hi) のように片側だけ含む範囲の書き方。境界の間違いが減る
総当たり(ブルートフォース)候補を全部試す。この記事ではアルゴリズムの話だけを指します
オラクル「正しい答え」を出す遅い実装。速い実装の検算に使う

① 準備 — 測る土台を作る

実験用のフォルダを作ります。 最後に消します。

bash
$ mkdir -p ~/cslab/search
$ cd ~/cslab/search
$ node -v
v22.14.0

node が無ければ、Node.js を入れる手順 を先に見てください。

測る道具を作ります。1回だけ測らないことが大事です。

bash
$ nano bench.mjs
// 何回か回して「中央値」を返す。1回だけだとブレる。
export function bench(fn, runs = 7) {
  const times = [];
  for (let i = 0; i < runs; i++) {
    const t0 = performance.now();
    fn();
    times.push(performance.now() - t0);
  }
  times.sort((a, b) => a - b);
  return times[Math.floor(times.length / 2)]; // 中央値
}

// 0 〜 n*10 のランダムな整数を n 個
export function randomData(n) {
  const a = new Array(n);
  for (let i = 0; i < n; i++) a[i] = Math.floor(Math.random() * n * 10);
  return a;
}

平均ではなく中央値を使います。 たまに走る GC が1回混ざるだけで、平均は簡単に壊れます。


② 線形探索 — 最良・平均・最悪は本当に違う

前から順に見るだけです。

bash
$ nano linear.mjs
import { bench } from "./bench.mjs";

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

const n = 1_000_000;
const arr = new Array(n);
for (let i = 0; i < n; i++) arr[i] = i;

const cases = [
  ["先頭にある", arr[0]],
  ["真ん中にある", arr[n >> 1]],
  ["末尾にある", arr[n - 1]],
  ["そもそも無い", -1],
];

console.log("件数:", n.toLocaleString());
for (const [name, target] of cases) {
  const ms = bench(() => linearSearch(arr, target));
  console.log(`${name.padEnd(14)} ${ms.toFixed(3)} ms`);
}
bash
$ node linear.mjs
件数: 1,000,000
先頭にある      0.000 ms
真ん中にある    0.244 ms
末尾にある      0.487 ms
そもそも無い    0.489 ms

ここが線形探索の性格です。

場合見る回数計算量
先頭にある1回O(1)(最良)
真ん中にあるn/2 回O(n)(平均)
末尾 / 無いn 回O(n)(最悪)

「無かった」を確定させるには、必ず最後まで見るしかありません。 見落としが無いことを、他に確かめる方法が無いからです。

そして、これが最大の強みです。

並んでいなくても使える。前処理が1秒も要らない。


③ 二分探索 — 100万件が20回で届く

真ん中を見て、半分を捨てます。

bash
$ nano binary.mjs
export function binarySearch(arr, target) {
  let lo = 0;
  let hi = arr.length - 1;
  let steps = 0;
  while (lo <= hi) {
    steps++;
    const mid = lo + ((hi - lo) >> 1);
    if (arr[mid] === target) return { index: mid, steps };
    if (arr[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return { index: -1, steps };
}

const n = 1_000_000;
const arr = new Array(n);
for (let i = 0; i < n; i++) arr[i] = i; // 並んでいる

for (const t of [0, 499_999, 999_999, -1]) {
  const r = binarySearch(arr, t);
  console.log(`target=${String(t).padStart(7)}  index=${String(r.index).padStart(7)}  ${r.steps} 回`);
}
console.log("log2(1,000,000) =", Math.log2(n).toFixed(2));
bash
$ node binary.mjs
target=      0  index=      0  19 回
target= 499999  index= 499999  1 回
target= 999999  index= 999999  20 回
target=     -1  index=     -1  19 回
log2(1,000,000) = 19.93

100万件が、最大20回。 計算と一致しました。

「半分ずつ捨てる」は「何回半分にできるか」で、それが log2 n です。 計算量の回で見た対数の伸び方が、そのまま出ています。

件数を増やしても、ほとんど増えません。

件数最大の回数
1,00010
1,000,00020
1,000,000,00030

1000倍にして、10回増えるだけです。

スクリーンショットを撮ってください: 01_binary_steps.png node binary.mjs の出力と、log2(1,000,000) = 19.93 が並んでいる画面を撮ってください。


④ 実装を3回間違える

二分探索は「10行なのに書けない」で有名です。 私も3つとも踏みました。わざと踏んでから直します。

bash
$ nano bugs.mjs

間違い1: Math.floor を忘れる

// ⚠️ 壊れている版
function bad1(arr, target) {
  let lo = 0, hi = arr.length - 1;
  while (lo <= hi) {
    const mid = (lo + hi) / 2;   // ← 小数になる
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return -1;
}

const a = [1, 3, 5, 7, 9, 11, 13, 15];
console.log("bad1(a, 9)  =", bad1(a, 9));
bad1(a, 9)  = -1

あるはずの 9 が見つかりません。

理由は arr[3.5] が undefined だからです。エラーにならないので、気づきにくい。

console.log("a[3.5] =", a[3.5]);   // undefined
console.log("undefined < 9 →", undefined < 9);   // false
console.log("undefined > 9 →", undefined > 9);   // false
a[3.5] = undefined
undefined < 9 → false
undefined > 9 → false

undefined はどちらの比較も false になるので、常に「大きいほう」の枝に進んで、静かに間違えます。

直し方:

const mid = lo + ((hi - lo) >> 1);

(lo + hi) / 2 ではなく lo + ((hi - lo) >> 1) と書く癖を付けます。 JavaScript では >> が整数化までやってくれます。そして 他の言語では、lo + hi が最大値を超えて桁あふれするという有名なバグを、この書き方が同時に防ぎます。

間違い2: < と <= を取り違える

// ⚠️ 壊れている版
function bad2(arr, target) {
  let lo = 0, hi = arr.length - 1;
  while (lo < hi) {              // ← `<=` であるべき
    const mid = lo + ((hi - lo) >> 1);
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return -1;
}

console.log("bad2(a, 1)  =", bad2(a, 1));
console.log("bad2(a, 15) =", bad2(a, 15));
bad2(a, 1)  = -1
bad2(a, 15) = -1

端を含む、一部の値が見つかりません。 この配列では 1・5・9・15 の4つです(13 などは見つかります)。

hi = arr.length - 1 は含む端なので、lo === hi の1個だけ残った状態も調べる必要があります。while (lo < hi) だとそこで抜けてしまいます。

この取り違えは、次の組み合わせで起きます。

hi の初期値ループ条件正しいか
arr.length - 1(含む)lo <= hi正しい
arr.length - 1(含む)lo < hi端が漏れる
arr.length(含まない・半開区間)lo < hi正しい
arr.length(含まない)lo <= hi範囲外を読む

どちらか一方に決めて、二度と混ぜないのが唯一の対策です。 私は半開区間 [lo, hi) に統一しました。hi = arr.length と while (lo < hi) の組です。

間違い3: lo も hi も動かない

// ⚠️ 無限ループになる版(実行しないでください)
//   const mid = lo + ((hi - lo) >> 1);
//   if (arr[mid] < target) lo = mid;      // ← mid + 1 でない
//   else hi = mid;

これは実際に走らせないでください。 ターミナルが固まります。

lo と hi が隣り合ったとき、mid は必ず lo になります。そこで lo = mid と書くと lo が変わらず、永久に同じ場所を見続けます。

確かめ方は、走らせることではなく数えることです。

// ループ回数に上限を付けておくと、無限ループが「例外」になって気づける
let guard = 0;
while (lo < hi) {
  if (++guard > 64) throw new Error("回りすぎ: 実装が間違っている");
  // ...
}

log2(配列の長さ) を超えたら、必ず実装が間違っています。 64回で止めておけば、固まらずにエラーで教えてくれます。

直した版と、lower_bound

実務で本当に欲しいのは、こちらです。

bash
$ nano lower.mjs
// target 以上が最初に現れる位置を返す。
// 見つからなくても「そこに入れれば順序が保たれる」位置が返る。
export function lowerBound(arr, target) {
  let lo = 0;
  let hi = arr.length;          // 半開区間 [lo, hi)
  while (lo < hi) {
    const mid = lo + ((hi - lo) >> 1);
    if (arr[mid] < target) lo = mid + 1;
    else hi = mid;
  }
  return lo;
}

const a = [1, 3, 5, 7, 9, 11, 13];
for (const t of [0, 5, 6, 13, 99]) {
  const i = lowerBound(a, t);
  const hit = a[i] === t;
  console.log(`t=${String(t).padStart(2)}  位置=${i}  ${hit ? "見つかった" : "ここに入れる"}`);
}
bash
$ node lower.mjs
t= 0  位置=0  ここに入れる
t= 5  位置=2  見つかった
t= 6  位置=3  ここに入れる
t=13  位置=6  見つかった
t=99  位置=7  ここに入れる

-1 を返す版より、こちらのほうが使い道が広いです。

  • 並び順を保ったまま挿入する位置が、そのまま返る
  • 「◯◯以上を全部取り出す」の開始位置になる(範囲検索)
  • 同じ値が複数あるとき、最初の1つの位置になる

-1 を返す版は、この情報を捨てているだけです。

スクリーンショットを撮ってください: 02_lower_bound.png node lower.mjs の「見つかった / ここに入れる」が並んだ出力を撮ってください。


⑤ 一番大事な節: 並べる時間を勘定に入れる

ここが、私が間違えた場所です。

二分探索を使うには、先に並べないといけません。 その時間は誰が払うのか。

やり方前処理1回引くたび
線形探索なしO(n)
ソート + 二分探索O(n log n)(1回だけ)O(log n)

k 回引くときの合計は、こうなります。

線形:   k × n
二分:   n log n  +  k × log n

k が小さいうちは、左が勝ちます。 どこで入れ替わるのかを、実際に測ります。

bash
$ nano crossover.mjs
import { bench, randomData } from "./bench.mjs";
import { linearSearch } from "./linear.mjs";

function binarySearchPlain(arr, target) {
  let lo = 0, hi = arr.length;
  while (lo < hi) {
    const mid = lo + ((hi - lo) >> 1);
    if (arr[mid] < target) lo = mid + 1;
    else hi = mid;
  }
  return arr[lo] === target ? lo : -1;
}

const n = 200_000;
const data = randomData(n);
// 実在する値を混ぜた検索キーを用意しておく(毎回同じ条件で測るため)
const keys = Array.from({ length: 2000 }, (_, i) => data[(i * 97) % n]);

console.log(`件数 ${n.toLocaleString()}`);
console.log("k(引く回数) | 線形の合計 | ソート+二分の合計 | 速いのは");

for (const k of [1, 2, 5, 10, 20, 50, 100, 300, 1000]) {
  const ks = keys.slice(0, k);

  const linearMs = bench(() => {
    for (const key of ks) linearSearch(data, key);
  }, 3);

  const binaryMs = bench(() => {
    const sorted = [...data].sort((a, b) => a - b);   // ← 前処理も毎回含める
    for (const key of ks) binarySearchPlain(sorted, key);
  }, 3);

  const winner = linearMs < binaryMs ? "線形" : "二分";
  console.log(
    `${String(k).padStart(11)} | ${linearMs.toFixed(1).padStart(10)} ms | ` +
    `${binaryMs.toFixed(1).padStart(17)} ms | ${winner}`
  );
}
bash
$ node crossover.mjs
件数 200,000
k(引く回数) | 線形の合計 | ソート+二分の合計 | 速いのは
          1 |        0.1 ms |              14.6 ms | 線形
          2 |        0.2 ms |              14.6 ms | 線形
          5 |        0.5 ms |              14.6 ms | 線形
         10 |        1.0 ms |              14.7 ms | 線形
         20 |        2.0 ms |              14.7 ms | 線形
         50 |        5.1 ms |              14.7 ms | 線形
        100 |       10.2 ms |              14.8 ms | 線形
        300 |       30.5 ms |              15.0 ms | 二分
       1000 |      101.6 ms |              15.6 ms | 二分

交差点は、k = 100 と 300 のあいだにありました。

200,000件のデータを、150回未満しか引かないなら、並べないほうが速い。

私が最初に書いたコードは k = 1 でした。 表の一番上の行です。146倍遅くしていたことになります。

この表の読み方

  • ソート+二分の列が、k を増やしてもほとんど動いていないことに注目してください。14.6 → 15.6 ms。増えた1ms が、1000回分の探索です
  • 線形の列は、k に正比例しています。0.1 × k で、きれいに合っています
  • 並べるコストは1回だけ。だから引く回数が増えるほど、割り勘が効いていきます

判断はこうなります。

状況どちらか
1回だけ探す線形探索。並べるだけ損
データが毎回変わる(作っては捨てる)線形探索。並べ直しが毎回発生する
同じデータを何度も引く並べて二分探索
データは変わらず、引く回数が読めない並べておく。1回の準備で、以後ずっと安い

「速いアルゴリズム」を選ぶ前に、「何回呼ばれるのか」を数える。 これが順番です。 本線の速くする前に必ず測る — パフォーマンス改善とEXPLAIN と、同じことを言っています。

スクリーンショットを撮ってください: 03_crossover.png 「速いのは」の列が 線形 → 二分 に切り替わっている行が写るように撮ってください。


⑥ ハッシュと比べる — 順序が要るか、要らないか

並べる以外にも、前処理はあります。

bash
$ nano compare.mjs
import { bench, randomData } from "./bench.mjs";

const n = 200_000;
const data = randomData(n);
const keys = Array.from({ length: 1000 }, (_, i) => data[(i * 97) % n]);

// ① 何もしない
const includesMs = bench(() => {
  for (const k of keys) data.includes(k);
}, 3);

// ② 並べて二分探索
const sortMs = bench(() => {
  const sorted = [...data].sort((a, b) => a - b);
  for (const k of keys) {
    let lo = 0, hi = sorted.length;
    while (lo < hi) {
      const mid = lo + ((hi - lo) >> 1);
      if (sorted[mid] < k) lo = mid + 1; else hi = mid;
    }
  }
}, 3);

// ③ Set に入れる
const setMs = bench(() => {
  const set = new Set(data);
  for (const k of keys) set.has(k);
}, 3);

console.log(`件数 ${n.toLocaleString()} / 1000回引く`);
console.log("includes            ", includesMs.toFixed(1), "ms");
console.log("sort + 二分探索      ", sortMs.toFixed(1), "ms");
console.log("Set に入れて has     ", setMs.toFixed(1), "ms");
bash
$ node compare.mjs
件数 200,000 / 1000回引く
includes             101.9 ms
sort + 二分探索       15.6 ms
Set に入れて has       4.3 ms

Set が一番速い。 ハッシュの前処理は O(n) で、ソートの O(n log n) より安いからです。

では、いつもハッシュでよいのか。違います。

問いSet / Map並べて二分探索
これ、ある?できる(最速)できる
50以上の値を全部できない(全件見るしかない)できる(範囲検索)
一番小さい値できないできる(先頭)
順番に取り出す挿入順のみ大小の順
その値に一番近いものできないできる(lowerBound の前後)
前処理O(n)O(n log n)

一本の軸はこれです。

「これ、ある?」しか聞かないならハッシュ。「◯◯以上」「一番近いもの」を聞くなら、並べる。

データベースの索引が、まさにこの選択です。 ハッシュ索引は等値比較しかできず、B木索引は範囲検索もできる。だから既定は B木になっています。詳しくは 索引を張ったのに使われない — SQL深掘り に書きました。


⑦ 総当たり — 「思いつかないとき」の正解

総当たり(ブルートフォース)は、候補を全部試すやり方です。

この記事で言う総当たりは、アルゴリズムの話だけです。 他人の認証を破る話ではありません。

まず、破綻する規模を知ります。

bash
$ nano bruteforce.mjs
// n 個の都市を回る順番は (n-1)! 通り。全部試すと何通りか。
function factorial(n) {
  let r = 1n;
  for (let i = 2n; i <= BigInt(n); i++) r *= i;
  return r;
}

console.log("都市の数 | 試す順番の数");
for (const n of [5, 8, 10, 12, 15, 20]) {
  console.log(String(n).padStart(8), "|", factorial(n - 1).toLocaleString());
}
bash
$ node bruteforce.mjs
都市の数 | 試す順番の数
       5 | 24
       8 | 5,040
      10 | 362,880
      12 | 39,916,800
      15 | 87,178,291,200
      20 | 121,645,100,408,832,000

20都市で 1.2 × 10^17 通り。 1秒に1億通り試せても、38年かかります。

総当たりは、ここで止まります。

それでも総当たりが正解になる2つの場面

1つ目: 候補が少ないとき。

10都市なら36万通りです。手元で1秒もかかりません。規模が小さいなら、総当たりが最も速く書けて、最も間違えにくい。 賢い実装を1時間かけて書いてバグらせるより、ずっとよい。

2つ目が本題です。速い実装の検算に使う。

bash
$ nano oracle.mjs
import { lowerBound } from "./lower.mjs";

// 遅いけれど、確実に正しい実装(オラクル)
function lowerBoundSlow(arr, target) {
  for (let i = 0; i < arr.length; i++) if (arr[i] >= target) return i;
  return arr.length;
}

// ランダムなデータと問い合わせを大量に作って、2つの実装を突き合わせる
let ng = 0;
for (let trial = 0; trial < 20000; trial++) {
  const n = Math.floor(Math.random() * 12);
  const arr = Array.from({ length: n }, () => Math.floor(Math.random() * 20)).sort((a, b) => a - b);
  const t = Math.floor(Math.random() * 22) - 1;

  const fast = lowerBound(arr, t);
  const slow = lowerBoundSlow(arr, t);
  if (fast !== slow) {
    ng++;
    if (ng <= 3) console.log("不一致:", JSON.stringify(arr), "t =", t, "→ 速い:", fast, "遅い:", slow);
  }
}
console.log(ng === 0 ? "20000件すべて一致" : `${ng} 件が不一致`);
bash
$ node oracle.mjs
20000件すべて一致

これが総当たりの一番の使い道です。

④で踏んだ3つの間違いは、全部このやり方で見つかります。 実際、bad2 を通すとこうなります。

不一致: [3] t = 3 → 速い: -1 遅い: 0
不一致: [1,4] t = 4 → 速い: -1 遅い: 1
不一致: [2,7,9] t = 9 → 速い: -1 遅い: 2

「端が漏れる」というバグが、最小の反例つきで出てきました。 頭で考えるより速い。

空の配列・1件の配列・全部同じ値・端の値といった、自分では思いつかない入力を、ランダムが勝手に作ってくれます。

実務で見かける探索

場面中身
DB の索引B木。二分探索の親戚(枝が多い版)。索引が「速い」の正体
git bisect二分探索そのもの。1000コミットから壊れた1つを10回で見つける
部分一致の検索索引が効かない。全文検索とMeilisearch
Set / Mapハッシュ。等値だけ

git bisect を実際に見てみます。

bash
$ git bisect start
$ git bisect bad          # いまは壊れている
$ git bisect good HEAD~50 # 50個前は動いていた
Bisecting: 24 revisions left to test after this (roughly 5 steps)

roughly 5 steps と言っています。 50個を5〜6回で絞り込む。log2(50) ≈ 5.6 です。

やめるときは必ずこれを打ちます。

bash
$ git bisect reset

reset を忘れると、中途半端なコミットをチェックアウトしたまま作業を続けることになります。 私はこれで一度混乱しました。Gitの導入と最初の設定 と合わせてどうぞ。


つまずいたところ

「二分探索のほうが速い」を、条件を付けずに覚えていた。 これが導入で書いた失敗の全部です。アルゴリズムの速さは、必ず「前処理」と「呼ばれる回数」とセットで考えると決めました。

(lo + hi) / 2 が動いてしまった。 配列が小さいうちは mid がたまたま整数になるので、テストが通ってしまいます。⑦のランダム検算を回して、初めて落ちました。小さい手書きのテストは、境界のバグを通します。

while (lo <= hi) と hi = arr.length を混ぜた。 範囲外を読んで undefined が返り、-1 になりました。「含む端」と「含まない端」を混ぜたのが原因で、半開区間に統一したら二度と起きなくなりました。

無限ループでターミナルが固まった。 Ctrl+C で止まらず、別の端末から pkill node しました。それ以来、探索のループには必ず回数の上限を入れています。 64回を超えたら例外にすれば、固まらずに教えてくれます。

bench を1回しか回していなくて、結果がひっくり返った。 同じコードなのに、走らせるたびに「線形が速い / 二分が速い」が変わりました。中央値を取るようにして安定しました。 それでも測るたびに交差点は少し動きます(このマシンでは 100〜300 のあいだ)。桁を見るのであって、1の位を見るのではありません。

交差点の実験で、ソートを測定の外に置いていた。 それだと「二分探索が常に速い」という当たり前の結果しか出ません。bench の中にソートを入れたところで、初めて正しい比較になりました。 何を測っているのかを毎回書き出す癖が要ります。

data.includes(k) が思ったより速かった。 100万件でも0.5ms 程度です。includes そのものは遅くありません。遅いのは「ループの中で includes を呼ぶ」形で、そこで初めて O(n²) になります。犯人を取り違えていました。

git bisect reset を忘れた。 切り分けが終わったあと、そのまま次の作業を始めて「なぜ自分の変更が消えているのか」と混乱しました。git bisect は必ず reset まで1セットです。


後片づけ

実験用フォルダを消します。

bash
$ cd ~
$ rm -rf ~/cslab/search
$ ls ~/cslab

search が消えていれば完了です。

git bisect を試した人は、忘れずに戻してください。

bash
$ git bisect reset
$ git status
On branch main
nothing to commit, working tree clean

元のブランチに戻っていることを確認します。


まとめ — 理解できたこと

  • 線形探索の強みは速さではなく、「並んでいなくてよい」こと。 前処理が0
  • 「無かった」を確定させるには、必ず最後まで見るしかない
  • 二分探索は毎回半分捨てるので、100万件が20回。 1000倍にして10回増えるだけ
  • (lo + hi) / 2 は書かない。 lo + ((hi - lo) >> 1) にする。小数の添字は undefined を返し、エラーにならずに静かに間違える
  • 「含む端」と「含まない端」を混ぜない。 半開区間 [lo, hi) に統一する
  • ループに回数の上限を入れておくと、無限ループが例外になって気づける
  • 実務で欲しいのは lower_bound。 見つからなくても「入れるべき場所」が返り、範囲検索の起点にもなる
  • 一番大事: ソートの時間を勘定に入れる。 200,000件を 150回未満しか引かないなら、並べないほうが速い
  • 実測した合計時間: 線形は k に正比例(0.1 × k ms)、ソート+二分は k を1000倍にしても 14.6 → 15.6 ms
  • 私が最初に書いたコードは k = 1。146倍遅くしていた
  • 「これ、ある?」しか聞かないならハッシュ。「◯◯以上」「一番近いもの」を聞くなら並べる
  • DBの索引が既定でB木なのは、範囲検索ができるから
  • 総当たりは敗北ではない。 候補が少ないなら最善で、速い実装の検算(オラクル)としては最強
  • ランダムな入力で速い版と遅い版を突き合わせると、境界のバグが最小の反例つきで出てくる
  • git bisect は二分探索そのもの。 使ったら 必ず git bisect reset

参考リンク


次に読む

この記事は 【深掘り】コンピュータ科学 の 12 / 25 本目です。

記事
← 前の記事ソートアルゴリズム6種 — 並べ替えたら10が2の前に来た
→ 次の記事グラフとBFS・DFS — 循環参照で探索が止まらない

上から順に読めば積み上がるように並べています。 飛ばしても構いませんが、詰まったら前の回に戻ってください。

全体の順路は はじめに にあります。

roadmap.sh のどこをやっているか

›CS — Searching
  • 並べる時間を勘定に入れる
  • lower_bound と総当たりの使い道

この記事は、上の項目を実際に手を動かして確かめる回です。

よかったらシェアしてね!
  • URLをコピーしました!
  • URLをコピーしました!

コメント

コメントする

目次