線形検索と二分検索（計算量）
意味・解説
目的のデータを探し出す2つのアルゴリズムと、データ量（n）に対する最大比較回数の違い。
線形検索は先頭から順に探し、最大 $n$ 回比較する。二分検索はデータを半分ずつに絞り込み、最大 $\log_2 n$ 回比較する。二分検索はデータが昇順または降順に並んでいることが前提条件。
くわしく
「探し物の効率」の計算です。
1.線形検索：
データがバラバラでも使えますが、量が増えると手間も同じだけ増えます。
2.二分検索：
整理されたデータから「真ん中」を見て、前後どちらか半分を捨てる作業を繰り返します。ポイントは、データが100万件あったとき、線形なら最大100万回かかるところ、二分検索ならわずか20回程度で済むという「劇的な効率の差」があるからです。
例文
大量の顧客リストから特定の氏名を高速に検索するため、データをあらかじめソートしておき、二分検索アルゴリズムを実装した。
同義語: 逐次検索（線形検索の別名）
分類: 探索アルゴリズム