2 分探索にぶんたんさく

2 分ぶん探索たんさく（Binary Search）は、整列せいれつ済ずみデータの中央ちゅうおうの値あたいと目的もくてきの値あたいを比較ひかくし、探索たんさく範囲はんいを毎回まいかい半分はんぶんに絞しぼり込こんで目的もくてきの値あたいを探さがすアルゴリズムです。計算けいさん量りょうは $O(\log N)$ で、先頭せんとうから順じゅんに調しらべる 線形探索せんけいたんさく（$O\left(N\right)$）より圧倒的あっとうてきに高速こうそくです。

観点かんてん	2 分ぶん探索たんさく	線形探索せんけいたんさく（線形せんけい探索たんさく）
計算けいさん量りょう	$O(\log N)$	$O\left(N\right)$
前提ぜんてい	整列せいれつ済ずみが必須ひっす	整列せいれつ不要ふよう
比較ひかく回数かいすう（1000 件けん）	約やく 10 回かい	最大さいだい 1000 回かい

中央ちゅうおうの要素ようそと比くらべて、目的もくてきの値あたいが小ちいさければ前半ぜんはん、大おおきければ後半こうはんだけを次つぎの探索たんさく範囲はんいにします。たとえば 1000 件けんのデータでも、半分はんぶん・半分はんぶん…と絞しぼるので最大さいだい 10 回かい程度ていどの比較ひかくで見みつかります（$2^{10}=1024$ のため）。

試験しけんでは 「整列せいれつ済ずみが前提ぜんてい」「1 回かいごとに範囲はんいが半分はんぶん」「計算けいさん量りょう$O(\log N)$」の 3 点てんと、線形せんけい探索たんさくとの対比たいひが頻出ひんしゅつです。