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

二分探索の候補区間を紙に残す

    解き方


    『目標があれば、その位置は今の候補区間に含まれる』という条件を保ちながら読みます。中央を調べて不一致だった場合、次の区間から中央も外します。


    確認問題【オリジナル】


    lo ← 1
    hi ← n
    while lo ≦ hi
      mid ← (lo + hi) ÷ 2 の整数部分
      if A[mid] = target
        return mid
      elseif A[mid] < target
        lo ← 【空欄】
      else
        hi ← mid − 1
      endif
    endwhile
    return 0


    昇順の A=[2, 5, 9, 14, 20]から16を探します。空欄を埋めて、調べる要素番号と返り値を答えてください。


    答えと解説


    空欄は mid+1 です。調べる番号は3、4、5です。候補区間は[1,5]→[4,5]→[5,5]→[5,4]と変わり、最後は空になって0を返します。lo ← mid では、候補が1件のときに区間が縮まらない場合があります。


    IPA 科目Bのサンプル問題(出題形式の参考)

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

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

    あなたへのおすすめ