テクノロジ
線形探索とは
英語名：Linear Search
ひとことで言うと：先頭などから要素を一つずつ順番に比較し、目的の値を探す探索方法。
意味をわかりやすく解説
線形探索はデータが整列されていなくても利用でき、実装が単純です。目的値が見つかればその時点で終了し、存在しない場合や末尾にある場合は全要素を調べることになります。
要素数をnとすると比較回数は最悪n回程度で、計算量はO(n)です。データ件数が非常に多い場合には、整列済みなら二分探索などが有利になります。
具体例
配列[17,4,25,9,12]から9を探すと、17→4→25→9と順に比較して4回目で見つかります。
似た用語との違い
二分探索
線形探索は順に調べ、未整列でも使えます。二分探索は整列済みデータの範囲を半分ずつ絞ります。
基本情報技術者試験の試験ポイント
未整列でも使える代わりに、最悪では全要素を調べます。O(n)の意味を理解します。
CHECK QUESTION
100件の配列に目的値が存在しない場合、単純な線形探索では最大何件を調べますか。
答えを見る
100件です。存在しないことを確認するには全要素を調べる必要があります。
この説明は分かりやすかったですか？
基本情報技術者試験を勉強中ですか？
この用語を含む重要用語を、単語帳や4択テストで学習できます。