【擬似言語⑥】線形探索法 | 番兵法（基本情報技術者, 科目B, アルゴリズム）

このNoteのテーマは、探索法。「擬似言語の中ボス」的位置。データ群からお目当てのデータを見つけます。

今までの「データ配列を引数で受ける」「初期値を検討する」から、「番兵法」「配列の拡張ができない」を新しく学習します。

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

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

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

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

❶線形探索法 | 先頭から探していく

「データ配列から、お目当ての値を見つけて、配列の何番目に保管されているのかを表示する」擬似言語を作ります。

配列の先頭から順番に「探してる値かな？」と見ていく方式を「線形探索法」と云います。

〇 linearSearch(整数型の配列: data, 整数型: target)
  整数型: result
  整数型: i

  / data[1]から最後まで、順番にtargetを探す */
  for (i を 1 から dataの要素数 まで 1 ずつ増やす)
    / もし探しているデータ（target）が見つかったら */
    if (data[i] = target)
      result ← i  / 見つかった位置を記録 */
    endif
  endfor

  result を表示する

アパートを1部屋ずつ開けては住民を確認するような感じ（リアルでは迷惑💦）

linearSearch({1, 3, 5}, 1)の時、「1」がdata[1]に見つかったので、「1」が表示されます。linearSearch({1, 3, 5}, 3)なら、「3」がdata[2]に見つかったので「2」が表示。

気がかりな点があります。

• linearSearch({1, 2, 3, 4, 5}, 1)の動作
  →「1」が見つかったら、探索止めよ？（❷節で検討）

• linearSearch({1, 2}, 3)の動作
  →「3」が見つからないけど？（➌節で検討）

❷見つかった場合への対応（改）

linearSearch({1, 2, 3, 4, 5}, 1)の時、データ1番目で早々にお目当ての「1」が見つかりました。

「2, 3, 4, 5って確認しなくても良いのでは？ もう見つかったんだし」と考えて、お目当てが見つかったら探索を止める→探索ループを離脱（break）するように改良してみます。

〇 linearSearch(整数型の配列: data, 整数型: target)
  整数型: result
  整数型: i

  for (i を 1 から dataの要素数 まで 1 ずつ増やす)
    if (data[i] = target)
      result ← i  / 見つかった位置を記録 */
      break       / 見つかったので、即終了！ */
    endif
  endfor

  result を表示する

linearSearch({1, 2, 3, 4, 5}, 1)の時、i=1の時に見つかりループを抜けます。i=2以降の処理はしません。

linearSearch({1, 2, 3, 4, 5}, 3)の時、i=1, 2, 3とループして、i=3で見つかるのでループ抜けます。i=4以降の処理はしません。

➌見つからなかった場合への対応

❷で改良したコード。linearSearch({1, 2}, 3)の時、まずいです。「resultを表示する」はどうなりますか？

〇 linearSearch(整数型の配列: data, 整数型: target)
  整数型: result
  整数型: i

  for (i を 1 から dataの要素数 まで 1 ずつ増やす)
    if (data[i] = target)
      result ← i  / 見つかった位置を記録 */
      break       / 見つかったので、即終了！ */
    endif
  endfor

  result を表示する

i=1, 2の処理をしますが、「3」はdata配列内にないので見つからず「result ← i」は実行されず、ループが終了します。

「整数型: result」の宣言以降、何も代入されてないので。前のゴミデータや欠片か,　そもそも空っぽだったのか。

「初期化」が必要でしたね。＞【擬似言語③】合計のNote

〇 linearSearch(整数型の配列: data, 整数型: target)
  整数型: result ← -1  / 見つからなかったとき（-1） */
  整数型: i

  for (i を 1 から dataの要素数 まで 1 ずつ増やす)
    if (data[i] = target)
      result ← i  / 見つかった位置を記録 */
      break       / 見つかったので、即終了！ */
    endif
  endfor

  result を表示する

「-1」で初期化した理由は「あり得ない値」だから。お目当てが見つかったら「1」や「2」など、resultは1以上の整数になります。配列の要素番号が1以上なので（data[1], data[2]…）。

「整数型: result ← 1」にしたらダメです。探す前から見つかった判定になってます。

他にも「while(True)」で無限ループにして、ループ内部で「break」させ離脱するなど。最初にキメウチして後で変更するテは使われますね。＞擬似言語の教科書Note（⑰反復の離脱）

➍番兵法 | 必ず見つかるように

「線形探索法」の工夫「番兵法」を学びます。

今までの線形探索法では、iが「dataの要素数」を超えてないかの判定が必要でした。

  for (i を 1 から dataの要素数 まで 1 ずつ増やす) / 毎回判定が必要 */
    if (data[i] = target)
      / ～略：見つかった時の処理～ */
    endif
  endfor

番兵法では、
data={1, 2, 3}、target=5の時、
data={1, 2, 3, 5}にします。
target(5)はdata[4]で見つかります。

targetが必ず見つかるので、ループ判定を「targetが見つかるまで続けろ」に単純化。data配列の要素数なんて気にせず、見つかる/見つからないだけに集中できます。

  while (data[i] ≠ target)
    i ← i + 1  / 見つからない間は、ただ次の箱に進むだけ！ */
  endwhile

必ずtargetが見つかるので、「dataの要素数を超えてないか」ってチェックが要りません。

ループ後に「どこで見つかった」か確認が必要。
data配列最後より前で見つかった→見つかった
data配列最後（追加target）で見つかった→見つからなかった

  if (i ≦ n)
    i を表示する      / 番兵にたどり着く前に見つかった */
  else
    -1 を表示する    / 番兵まで来ちゃった＝元々無かった */
  endif

全体の擬似言語。

〇sentinelSearch(整数型の配列: data, 整数型: target)
  整数型: n ← dataの要素数
  整数型: i

  / 配列の「最後の次」に、targetを仕込む（番兵） */
  dataの末尾に target を追加する

  / 配列内にtargetを見つけるまで探索 */
  i ← 1
  while (data[i] ≠ target)
    i ← i + 1  / 見つからない間は、次へ進むだけ！ */
  endwhile

  / ループが止まった場所が「データの中」か「番兵の場所」か判定 */
  if (i ≤ n)
    i を表示する      / 番兵にたどり着く前に見つかった（成功！） */
  else
    -1 を表示する    / 番兵の場所まで来ちゃった＝元々は無かった（失敗！） */
  endif

ここまでで、今回の学習目標は達しました。

まとめ

お疲れ様でした！

「番兵法」。習わないと思い付きもしませんね。プログラムならではの工夫でした。他にも、初期値「-1」にする復習もできました。
＞【擬似言語①】ホテルの料金計算のNote（エラー時の返り値）
＞【擬似言語③】合計のNote（初期化は大事）
＞【擬似言語⑤】最大値のNote（あり得ない値に）
＞擬似言語の教科書Note（⑰反復の離脱）

このシリーズは、＞【FEB】擬似言語の教科書Note の基礎を生かしつつ、考察と次回への布石を追加して「知識のリレー」を繋いでいくように作っています。

次回は、二重ループと二次元配列を学びます。結構簡単なのでプラスαをどう盛り込むか考え中。＞【擬似言語⑦】九九表 | 二次元配列のNote

やって欲しい課題。data配列にtarget値が複数ある場合に動作を考えてみてください。
例えば、data={1, 2, 1}でtarget(1)の時。
擬似言語❶で「3」が表示される。
擬似言語❷で「1」が表示される。
を確認してください。

やらなくても良い課題。擬似言語❶を改良して、targetが複数見つかる場合に対応した擬似言語を作ってください。data={1, 2, 1}でtarget(1)の時、「1, 3」が表示される感じ。➍の「～の末尾に～を追加する」を使ってOK（FE科目Bで使われる表現）。＞解説はLv.3以降でやるかも（未定＊）

さらに余談。「～の末尾に～を追加する」は、プログラム言語では結構特殊な処理です。配列は宣言時に要素数を指定するので、あとから追加/変更できないのが普通です。このあたりもLv.3以降かなぁ（未定＊）。

最後に私のお薦めの演習順番。

❶学習前の”分からせ”
＞【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（セキュリティ）