メインコンテンツへスキップ
見出し画像

線形探索と二分探索

    用語の意味


    線形探索は先頭から順に値を調べる方法です。二分探索は整列済みのデータで中央の値と目標値を比べ、候補を半分ずつに絞ります。


    使いどころと問題の見方


    昇順の配列で中央の値が目標より大きければ、中央より左だけを残します。見つからない場合に備え、候補区間が空になったら終了します。配列での最悪時の比較回数は、線形探索が要素数に比例するのに対し、二分探索は要素数の対数に比例します。


    確認問題【オリジナル】


    昇順の配列[2, 5, 9, 13, 21]から5を二分探索します。最初に9と比較した後、候補として残す値はどれですか。


    ア.2と5
    イ.9と13
    ウ.13と21
    エ.5と13


    正解と理由


    正解はアです。9は5より大きいため、9より左の2と5だけが候補に残ります。


    IPA 基本情報技術者試験シラバス

    この記事が参加している募集

     
     
    ITの知識ゼロから、基本情報技術者試験の勉強を始めました📚 わからなかった言葉や問題を、自分の言葉でまとめる備忘録です。 基礎からコツコツ学んで、いつかは応用情報にも挑戦したいです! 一緒に学んでいただけたらうれしいです🌱

    あなたへのおすすめ