【擬似言語⑥追ノ壱】２分探索法 | 本格トレースの始め（基本情報技術者, 科目B, アルゴリズム）

このNoteでは「2分探索法」を学習します。「探索法」は、データ群からお目当てのデータを探す（保管位置を特定）手法。＞【擬似言語⑥】線形探索法Note に続いて2種類目です。

図解を分かり易く描けたかなぁと思います。図だけでも見て「本腰入れて読んでやるかぁ」と思って頂けたら嬉しいです。

このNoteは、私がIT専門学校で授業したことを基に作成しています。IT専門学校でFEは第一目標として、カリキュラムが構築されています。何も知らずに入学しても、1年生10月にはFE合格していきますよ。実績ある教育ノウハウを詰め込んだので、少しでも信頼して頂けたら嬉しいです。

テキストの基礎を生かして、プログラム的な考察/工夫を学んでいきます。基礎と実用にギャップを感じる方のために作りました。
＞【FEB】擬似言語の教科書Note

ぜひ一緒に学習を進めていきましょう！

＞全Noteへのリンク（FE節）
※科目Aのテーマ別/科目B/旧FE午後など沢山作りました！

２分探索法の手順を理解

簡単なデータと具体的な手順を図解にしました。

「l」が探す左端（left）、「r」が右端（right）。「m」は中央（m）。

探すデータがmと一致すれば良し、一致しないならmより大きい/小さいを見て、次に探す範囲を右/左に絞ります。

探索を続ければ、いずれ「m」が探しモノと一致します。データ群れ存在しない時は、「l」が「r」も右側にハミ出ます。擬似言語の後に図解で解説しますね。

２分探索法の擬似言語

擬似言語を組みました。

探索を進める３変数（left, right, mid）がありますね。midの作り方、見つからなかった時に範囲変更（left/rightを変更）してる点を大体把握してみてください。

/ data内の要素は、昇順（小さい順）に並んでるとする*/
○ 整数型: binarySearch(整数型の配列: data, 整数型: target)
  整数型: left, right, mid, length
  length ← dataの要素数

  / 左端と右端*/
  left ← 1
  right ← length

  / 探索範囲の絞り込みながら探す */
  while (left ≦ right)
    mid ← (left + right) ÷ 2の商（小数点以下切り捨て）

    if (data[mid] ＝＝ target)
      return mid  / 目的の値が見つかったので、その要素番号を返す */
    elseif (data[mid] < target)
      left ← mid + 1  / midより右側を探索範囲にする */
    else
      right ← mid - 1 / midより左側を探索範囲にする */
    endif
  endwhile

  return -1  / 見つからなかった場合 */

midはleftとrightの中間（÷2）、midがtargetと一致すれば終了（return）。見つからなかったら、midとtargetを比べて左側に絞る（rightを更新）/右側に絞る（leftを更新）のが分かったでしょうか？

return文が2か所あるのが嫌だったら、「return mid」を「break」にして「return -1」をちょっと改良かな。「left ≧ right」だったら「return -1」、違ったら「return mid」とか。んー。書いたら却ってゴチャゴチャしそう。

次節から、簡単なデータを設定して動作を図解にしました。ご自分でも上記の擬似言語をトレースして見て頂けたら嬉しいです。下記がデータ（data）と探す値（target）の設定です。

• data={6, 7, 8, 9, 10}

  • target=9：右側で見つかるケース

  • target=7：左側で見つかるケース

  • target=11：データ見つからないケース

• data={6, 7, 9, 10, 11}, target=8：データが見つからないケース

トレース | 見つかる場合

探索範囲を右に絞って見つかるケース。無事2回目のmでtargetが見つかりました。

探索範囲を左に絞って見つかるケース。無事2回目のmでtargetが見つかりました。leftとrightが同じ[2]を指している時は、[2]だけが探す範囲って意味です。

擬似言語の数式で、変数（l, r, m）の値が変わり、指している配列位置が変わっている点が対応付けられればOKです。部屋番号と住人の区別です。

難しいですよね。

トレース | 見つからない場合（範囲外）

data[]にtargetが見つからないケースを準備しました。target=11は、data[]の最大値=10よりも大きくて見つからない。

最後。探索範囲の左端「l」が右端「r」よりも右にきちゃいました。これは「探索する場所がない」って意味です。「while(left ≦ right)」のループ継続条件を満たさなくなったので、ループ終了（探索終了）。

トレース | 見つからない場合（範囲内）

data[]内にtargetがないケース。今度は、値的にはdata[]内にありそうだけど、実際はなかった例。data[]は6～11なので、target=8はありそうだけど、なかった。

前節と同じく、探索範囲の左端「l」が右端「r」の更に右側になったので、「見つかりませんでした！」で探索終了です。

余談 | 切り捨て→切り上げの場合は？　カットかな。それか数行。

余談で曖昧なのでスキップしてOKです。

midの計算で「書数点以下切り捨て」を「切り上げ」にしたらどうなるか。

 mid ← (left + right) ÷ 2の商（小数点以下切り捨て）
 mid ← (left + right) ÷ 2の商（小数点以下切り上げ） 

自分で組んだ時、「切り上げ」にしちゃうことあると思います。別にどっちでも良いんじゃないかなって。

FE科目Bで「切り上げ」が使われた場面があります。「i←(p×(sortedDataの要素数-1)の小数点以下を切り上げた値)」＞【FEB】サンプル1問14のNote

逆にいえば、他に「切り上げ」を使った問題はなく。そもそも「切り捨て」はなかったです。

一応「切り上げ」にした場合もトレースして、大丈夫そうなのは確認はしました。「切り上げ」でも動きはしそうなので、「擬似言語レベルでは間違いではない（=正しい）」と思われます。

ただ、プログラム言語の動作まで考えると「切り上げ」って不自然だ、って事情があって「切り捨て」にしてます。＞整数型と実数型の数式（企画中＊）

余談だし混乱/誤解を招くのでここまでにしますが。気になる方は、プログラムで確認してみて下さい。

まとめ

お疲れ様でした！

前回の ＞線形探索法Note は先頭から探すので、データは大きさ順に並んでなくても使えました。その分探す回数が未定で、データがなければ全データを探す処理が全て徒労になってしまいます。

今回の 2分探索法は、データが大きさ順に並んでないと使えませんが、探す範囲を絞っていくので、効率化が出来ました。

どちらが優れてるとかじゃないんですが。代表的な探索法なので、擬似言語を理解/組めるようになって、メリット/デメリットまで語れると良いですね。

課題：data[]が降順（大きい順）に並んでる時の、二分探索の擬似言語を組んでください。ちゃんと簡単なデータでトレースもして下さいね。

こんな感じで、基礎を生かして実例で擬似言語を作って、さらにプログラム的な考察や工夫を深めていきたくて、理解シリーズを作ってます。＞【FEB】擬似言語の教科書Note

最後に私のお薦めの演習順番。
❶学習前の”分からせ”
＞【FEB】サンプル問題2のNote
❷テキスト
＞【FEB】擬似言語の教科書Note
＞【FEB】擬似言語の理解演習Note ←いまこの辺
↓※必要なら
うかる！ 基本情報技術者　[科目B・セキュリティ編](amazon)
うかる！ 基本情報技術者　[科目B・アルゴリズム編](amazon)
❸各年度の公開問題
＞【FEB】令和07年科目BのNote
＞【FEB】令和06年科目BのNote
＞【FEB】令和05年科目BのNote
➍解法の総復習（➋や➌と併用可）
＞【FEB】擬似言語の11の解法Note
➎模擬試験
＞【FEB】サンプル問題1のNote（擬似言語）
＞【FEB】サンプル問題1のNote（セキュリティ）