【情報I】探し方で速さは激変する。現役エンジニアが線形探索と二分探索を解説

こんにちは！オンライン家庭教師のこばやしです。普段はフリーランスのITエンジニアとして働きながら、中高生に「情報I」「理系数学」「英語」を教えています。

情報Iで学ぶ「線形探索」と「二分探索」。この2つの違いを、なんとなく暗記しているだけで、「なぜ二分探索のほうが速いのか」がいまいち納得できていない、という方も多いのではないでしょうか。

納得できない原因は、2つを言葉で覚えているからです。実際に仕組みを動かしてみれば、速さの差は一目瞭然！　今日はその"体感"をお届けします。

■ 線形探索は「端から順に」、二分探索は「半分に絞る」

まず、2つの探し方の違いを、辞書で「ある単語」を探す場面で考えてみましょう。

線形探索は、一ページ目から順番にめくって探す方法です。素朴で確実ですが、後ろのほうにある単語だと時間がかかります。一方二分探索は、まず真ん中を開いて「探している単語は前か後ろか」を判断し、探す範囲を半分に絞る。これを繰り返す方法です。

同じ「探す」でも、やり方がまるで違いますよね。

■ 二分探索の大前提は「並んでいること」

ここで一つ、大事な注意点があります。二分探索が使えるのは、データが順番に並んでいるときだけです。

辞書がアイウエオ順に並んでいるからこそ、「真ん中を見て前か後ろか」が判断できます。もしバラバラに並んでいたら、真ん中を見ても手がかりになりません。この「並んでいることが前提」というポイントは、試験でもよく狙われる盲点です。

■ 1万件で、差は"桁違い"になる

では、どれくらい速さが違うのか。データが1万件あるとします。

線形探索は、最悪の場合1万回も確認が必要です。ところが二分探索は、毎回半分に絞るので、なんと約14回で見つかります。1万回と14回。桁が違いますよね！　この差が、情報Iで学ぶ「計算量」の感覚です。データが増えれば増えるほど、この差はどんどん開いていきます。

■ 現場でも、"探し方"の選択が速度を決める

私が携わってきた金融決済システムでは、膨大なデータの中から目的の一件を探す処理が何度も出てきました。ここで探し方を間違えると、システム全体が遅くなってしまいます。

だからこそ、エンジニアは「このデータは並んでいるか？」「どの探し方が最適か？」を常に考えます。探し方の選択が、そのままサービスの快適さを決めるのです。

■ 「効率の差を考える力」は、あらゆる問題解決の基礎

「量が増えたときに、どれだけ効率が変わるか」を考える視点は、探索に限りません。勉強のやり方でも、仕事の進め方でも、「もっと効率のいい方法はないか」と考える力の土台になります。

私の授業では、実際に数を数えながら両者を比べ、「速さの差」を体で感じてもらいます。納得できると、計算量という抽象的な話が、ぐっと身近になります。

「二分探索がなぜ速いのか、いまいち納得できない」

「探索は暗記でなんとかしている」

そんな方は、ぜひ一度体験授業にいらしてください。「なるほど、だから速いのか！」という圧倒的な納得感と共に、アルゴリズムの面白さへご案内します！

【プロフィール】

こばやし｜納得感を大切にするフリーランスエンジニア

北海道大卒。約10年間にわたり金融決済システムなどの基幹開発に携わった後、フリーランスのエンジニア・IT講師として独立。企業の新人IT研修のメイン講師も務めるプロが、「仕組みから理解する」論理的な指導を行います。