「分かりそう」で「分からない」でも「分かった」気になれるIT用語辞典

それぞれの用語の意味

用語	意味
二分探索	「半分ずつ消去法」なデータの探し方。データが順番に並んでいる前提で、まずは真ん中のデータを取り出して「探しているデータは、これより大きい？」を確認する。もし「大きいよ！」だったら、真ん中のデータとそれより小さいデータを全部消す（「小さいよ！」だったら大きい方を消す）。残ったデータの中から真ん中のデータを取り出して「探しているデータは、これより大きい？」を確認する。……というのを繰り返すことで、条件に合わないデータを半分ずつ消していって、目的のデータを見つける やり方
線形探索	「端から順番に見ていくよ」なデータの探し方。まずは一番端のデータを取り出して「これが探しているデータかな？」を確認し、違ったらその隣のデータを取り出して「これが探しているデータかな？」を確認し、違ったらその隣のデータを取り出して「これが探しているデータかな？」を確認し……のように端から順番に見ていくことで目的のデータを見つける やり方

似ているところ

どちらもデータの探し方の名前です。

違うところ

探し方が違います。

二分探索は「半分ずつ消去法」な探し方です。
線形探索は「端から順番に見ていくよ」な探し方です。

詳細は、それぞれの用語の説明を ご覧ください。

それに伴い、メリット・デメリットが変わってきます。

二分探索のメリットは

１．データの量が増えても、そんなに探す時間が変わらない
２．探しているデータがどれでも、見つかるまでの時間が同じくらい

です。

二分探索では1回の絞り込みで候補が半分になります。
データが倍になっても絞り込みの回数は1回しか増えません。

例えば、10個の数字から1個の数字を探す場合、絞り込み回数は最大3回です。
倍の20個の数字の中から探すことになっても絞り込み回数は最大4回で済みます。
1回絞り込んだ時点で候補は（20個の半分の）10個になるからです。

また、二分探索では、探すデータがどれでも見つかるまでの時間が同じくらいです。

例えば、10個の数字から1個の数字を探す場合、絞り込み回数は最大で3回です。
「1」を探すのでも「8」を探すのでも（ピンポイントで真ん中の値に該当しない限り）絞り込み回数は3回になります。
探す値によって1回で済んだり100回もかかったりといったバラツキがありません。
検索にかかる時間を、ある程度は標準化できるのです。

二分探索のデメリットは

データが順番に並んでいないと使えない

です。

バラバラのデータに対して二分探索を使いたい場合は、順番を並べ直す必要があります。
順番を並べ直すのが大変な場合は、二分探索を使わない方が良かったりするわけです。

一方、線形探索のメリットは……なんでしょうね。
仕組みが単純なことでしょうか。
プログラミングとかで作り込むのが比較的、簡単です。

線形探索のデメリットは、探すのにどれくらいの時間がかかるか予想しにくいことです。
探しているデータが最初の方にあれば、すぐ見つかります。
探しているデータが後ろの方にあれば、中々見つかりません。
探しているデータの位置によって、探すのにかかる時間が大きく変わります。