二分探索

これはステージング環境です。5 秒後に自動的に本番環境 (https://dic.kimiyuki.net) にリダイレクトされます。リダイレクトを抑止したい場合は #noredirect を付けた URL /binary-search#noredirect を利用してください。
このページは下書きです。5 秒後に自動的にトップページ (https://dic.kimiyuki.net) にリダイレクトされます。リダイレクトを抑止したい場合は #noredirect を付けた URL /binary-search#noredirect を利用してください。
name
二分探索
short description
二分探索とは、ソート済みの列に対する探索アルゴリズムのひとつ。探索すべき区間の中央の要素を調べることで探索すべき区間の長さを半々にし、区間の長さ $N$ に対し $O(\log N)$ で位置を特定する。
input
長さ $N$ のソート済みの列 $a$ と検索対象の要素 $b$
output
$b$ が含まれる位置 $i$。あるいは、$b$ を挿入してもソート済みのまま保たれるような区間 $\lbrack l, r)$
time complexity
$O(\log N)$ など

話題