二分探索 (O(log n))

コンピューターサイエンス理論 / 全 5 枚

コンピューターサイエンス理論 - 二分探索 (O(log n))

半分ずつ捨てる

配列が小さい順に並んでいるなら、真ん中を1回見るだけで候補の半分を丸ごと捨てられます。捨てた側は二度と見ません。

並んでいることが前提です。並んでいない配列に使うと静かに間違えます。

lo と hi が挟む範囲が候補です。すれ違ったら、その値は無いと決まります。

let lo = 0, 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;

1 / 5

← → キーでも送れます

このスライドが付いているレッスンを開く