「線形探索と二分探索ってどちらもデータを探す方法じゃないの？」

応用情報技術者試験でもアルゴリズム分野で頻出ですが、

何が違うの？
どちらが速い？
二分探索はいつ使える？
計算量は？

で混乱する人がかなり多いテーマです。

この記事では、

線形探索とは？
二分探索とは？
違い
具体例
試験での頻出ポイント

を分かりやすく解説します！

まず結論

線形探索

「先頭から順番に探す」

二分探索

「真ん中から半分ずつ絞り込む」

超簡単にいうと

手法	探し方
線形探索	1つずつ確認
二分探索	半分ずつ削る

線形探索とは？

超頻出！

別名

逐次探索

方法

先頭から順番に比較する。

イメージ

データ

10 20 30 40 50

50を探す場合

10 → ×
20 → ×
30 → ×
40 → ×
50 → ○

特徴

重要！

並び順不要

どんなデータでも使える。

メリット

実装が簡単
ソート不要

デメリット

データが多いと遅い

二分探索とは？

超頻出！

方法

真ん中の値と比較する。

イメージ

データ

10 20 30 40 50 60 70

50を探す。

まず中央

と比較。

50 > 40

↓

左半分不要

残り

50 60 70

再び中央

と比較。

50 < 60

↓

右半分不要

残り

発見！

特徴

超重要！

ソート済みデータ限定

これが試験の定番問題。

線形探索と二分探索の違い

超頻出！

比較	線形探索	二分探索
探索方法	順番に確認	半分ずつ絞る
ソート必要	不要	必須
速度	遅い	速い
実装	簡単	やや複雑

イメージで理解

線形探索

本を1冊ずつ探す

二分探索

辞書を真ん中から開く

計算量

応用情報で頻出！

線形探索

O(n)

データ数に比例。

二分探索

O(log₂n)

半分ずつ減る。

計算量比較

例

100万件

線形探索

最大100万回

二分探索

約20回

圧倒的に速い！

いつ使う？

線形探索

未ソートデータ

二分探索

ソート済みデータ

試験での覚え方

超重要！

線形探索

全員に聞く

二分探索

半分ずつ消す

応用情報で超頻出

かなり狙われる👇

線形探索
二分探索
ソート済みデータ
計算量
O(n)
O(log n)

よくあるひっかけ

「二分探索はどんなデータにも使える」

→ ❌違う！

二分探索は

ソート済み

でなければ使えない。

1分で復習！

線形探索

順番に探す

二分探索

半分ずつ探す

線形探索

ソート不要

二分探索

ソート必須

超重要

O(n)

O(log n)

練習問題

問題

二分探索を行うための前提条件として最も適切なものはどれか。

ア

データが圧縮されている

イ

データが暗号化されている

ウ

データがソートされている

エ

データが重複していない

解答

正解：ウ

解説

二分探索は中央の値を基準に探索範囲を半分に絞るため、データが昇順または降順にソートされている必要があります。

まとめ

線形探索とは

「順番に探す」

二分探索とは

「半分ずつ探す」

超重要

線形探索＝O(n)
二分探索＝O(log n)
線形探索＝ソート不要
二分探索＝ソート必須

まずは、

「線形探索＝1人ずつ名前を聞く」

「二分探索＝辞書を真ん中から開く」

このイメージを持つとかなり理解しやすくなります！

リンク一覧（違い比較）はこちら

知識に自信ができた方は、今度は自身のキャリアアップに向けて準備してみませんか？

未経験から、ITエンジニアへ。

「IT業界に興味はあるけれど、自分にできるか不安」「何から始めればいいのか分からない」そんな方のために、Tech GO は未経験からのIT転職を専門的にサポートします。求人を紹介するだけではなく、あなたの強みを整理し、応募準備から入社後の成…

まずは無料でキャリア相談