科目Bの探索問題の解き方｜線形探索と二分探索の見分け方

探索の問題が出ると、どこまで調べ終わったのか分からなくなる。

添字が動くたびに、指で追うのをあきらめていませんか？

科目Bの探索問題は、ソートほど値が動きません。それでも迷う人が多いのは、調べる範囲が見えないまま読み進めてしまうからです。

でも大丈夫です。探索問題は型が2つしかなく、どちらなのかを最初に決めてしまえば、あとは決まった作業の繰り返しになります。

私はエンジニアとして10年以上、Webシステムの開発や運用に携わってきました。実務で探索を自分で書く場面は多くありませんが、条件の境界を一つ間違えて、データの最後の1件だけ見つからない不具合になる。これは何度も見てきました。

つまり探索でつまずくのは、頭の良さの問題ではありません。境界の扱いが細かいだけです。

この記事では、問題文の読み方から答え合わせまでを5つの段に分けてお伝えします。科目B全体の形をまだつかめていない人は、先に親記事に目を通しておくと理解が早くなります。

【関連記事】基本情報技術者試験の科目Bとは？擬似言語・アルゴリズム対策を初心者向けに解説

科目Bの探索問題は何を聞いているのか¶

まず、この分野で何が問われるのかをはっきりさせておきましょう。

探索問題で聞かれるのは、値が見つかったかどうかではありません。見つけるまでに何をしたか、です。

出題のされ方を整理すると、だいたい次の4つに収まります。

表を見て分かるとおり、どれも途中の動きを追っていないと答えが出ません。ここが探索問題の性格です。

見つかったときより、見つからないときが狙われる¶

正しい答えが配列の中にある場合は、素直に追えば終わります。試験が好んで聞くのは、目的の値が入っていないときの動きです。

範囲がゼロになった瞬間にどうなるか。そこを書き分けられるかどうかで差がつきます。

だから練習のときは、見つかる例と見つからない例を必ず両方追ってみてください。

探索の知識そのものは少なくていい¶

線形探索と二分探索の名前を覚えても、点数にはつながりません。問題文にアルゴリズムの名前が書かれていないことも珍しくないからです。

必要なのは、目の前のコードが範囲をどう狭めているかを読み取る力だけです。そこだけ見てください。

初めて見る形のコードが出てきたときの読み方は、こちらの記事でも扱っています。

【関連記事】科目Bの初見問題が解けない人へ｜知らないアルゴリズムが出たときの読み方

段1：線形探索と二分探索を見分ける¶

問題文を読み終えたら、1行目から追い始める前にコードの形だけを眺めます。見るのは添字の動き方です。

添字が1つずつ進むなら線形探索、真ん中を計算しているなら二分探索。この二択を先に決めてしまいます。

まず線形探索の例を見てみましょう。出題形式に合わせた自作のコードです。

○整数型: 線形探索(整数型の配列: data, 整数型: target)
  整数型: i
  for (i を 1 から data の要素数 まで 1 ずつ増やす)
    if (data[i] = target)
      return i
    endif
  endfor
  return -1

先頭から順に比べて、一致したらその場で添字を返しています。最後まで見つからなければ -1 を返す形です。

添字が1つずつ増えるなら線形探索¶

1 ずつ増やす と書かれたループの中で値を比べているなら、それは線形探索です。範囲は狭まらず、端から順に減っていきます。

このとき比較回数は、目的の値が何番目にあるかでそのまま決まります。3番目にあれば3回です。

見つからない場合は、要素数と同じ回数だけ比べることになります。ここは回数を聞く設問でよく使われます。

ループ回数そのものの追い方に不安がある場合は、先にこちらで固めておくと楽になります。

【関連記事】科目Bの繰返し問題が解けない人へ｜ループ回数を追うコツ

中央を計算する行があれば二分探索¶

(lo + hi) ÷ 2 のように2で割っている行を見つけたら、二分探索だと判断して構いません。真ん中を見て、調べる範囲を半分に捨てる型です。

二分探索には前提が一つあります。配列が並べ替えられていることです。問題文に整列済みと書かれているか、必ず確かめてください。

同じ探索の型を文法の側からもう一度確認したい人は、こちらの記事が対応しています。

【関連記事】擬似言語の線形探索と二分探索の違いとは？科目Bで差がつく探索の読み方

段2：まず目を付けるのは3か所¶

型が決まったら、次に読む場所を固定します。探索問題で見るべきところは3つだけです。

順番を決めておけば、長いコードでも迷子になりません。

この3か所を先に押さえてから、中身のトレースに入ります。

宣言を見れば型がほぼ決まる¶

変数が添字用の1つだけなら線形探索です。下限と上限にあたる変数が2つ宣言されていれば、範囲を狭める二分探索だと分かります。

宣言はコードの先頭にあるので、いちばん早く手に入る手がかりです。ここを飛ばさないでください。

return が2か所あるなら、両方の道を追う¶

探索のコードには、見つかったときの return と、見つからなかったときの return が別々に書かれます。

設問が聞いているのはどちらの道か、先に見極めてください。読む量が半分になります。

配列の添字の数え方そのものが不安な場合は、こちらの記事から先に読むのがおすすめです。

【関連記事】擬似言語の配列と添字がわからない人へ｜要素数・二次元配列の読み方を解説

段3：トレース表で調べる範囲を追う¶

ここからが本番です。二分探索は頭の中だけで追うと、ほぼ確実にどこかで崩れます。

書くのは3列の表です。下限、上限、真ん中の値を、1周ごとに1行足していきます。

二分探索のコードを見てみましょう。これも自作の例です。

○整数型: 二分探索(整数型の配列: data, 整数型: target)
  整数型: lo ← 1
  整数型: hi ← data の要素数
  整数型: mid
  while (lo ≦ hi)
    mid ← (lo + hi) ÷ 2 の商
    if (data[mid] = target)
      return mid
    elseif (data[mid] < target)
      lo ← mid + 1
    else
      hi ← mid - 1
    endif
  endwhile
  return -1

真ん中と比べて、目的の値が右にあるなら下限を上げ、左にあるなら上限を下げています。

lo と hi と mid の3列を書く¶

data が {2, 4, 7, 9, 12, 15} で、13 を探す場合を追ってみましょう。

4周目で lo が hi を追い越しました。この時点でループを抜け、-1 が返ります。

表にしてしまえば、6要素の探索が4行で終わります。この短さが二分探索の強みです。

トレース表の書き方そのものを丁寧に確認したい人は、専用の記事があります。

【関連記事】擬似言語のトレース表の書き方｜科目Bで変数の値を追う手順を解説

見つからない場合を1回だけ通しで追う¶

いま見たのは、目的の値が配列に無い例でした。わざとそうしています。

見つからない道を一度きちんと追っておくと、ループの終わり方が体に入ります。ここを通った経験があるかどうかで、本番の落ち着きが変わります。

範囲が半分になる速さを数字で確かめたい人は、計算量の記事も役に立ちます。

【関連記事】擬似言語の計算量（オーダー）とは？ループの回数から処理の速さを見積もる考え方を解説

段4：まぎらわしい選択肢の見分け方¶

探索問題の選択肢は、正解の隣に境界を1つずらした値が置かれます。作り方が決まっているので、知っておくと迷ったときに戻れます。

よくある外し方を表にまとめました。

いちばん上が圧倒的に多い間違いです。二分探索で lo ← mid と書くと範囲が狭まらず、永遠に終わらないコードになります。

判断に迷ったら、自分の表に戻ってください。表に出てこない値が選択肢にあるなら、追い方のどこかがずれています。

空欄補充なら、選択肢を表に入れて1周だけ回す¶

範囲を狭める行が空欄になっている問題では、考え込むより手を動かすほうが速いです。選択肢を当てはめて、表を1周ぶんだけ書いてみてください。

間違った選択肢を入れると、lo と hi が動かないか、逆に飛び越えてしまいます。その崩れ方が見えた時点で切れます。

線形探索の空欄なら、狙われるのはループの上限か、一致を判定する条件式です。どちらも1文字違いの選択肢が並ぶので、指を置いて読んでください。

段5：シミュレーターで動かして答え合わせをする¶

最後の段は、自分のトレースが正しかったかを確かめる作業です。ここを省くと、ずれた追い方が癖になってしまいます。

Giji Academy の擬似言語シミュレーターでは、いま見た探索のコードを1行ずつ実行して、lo と hi が動く様子を画面で追えます。無料で使えるので、紙の表と見比べてみてください。

擬似言語シミュレーターで探索のコードを動かしてみる

自分の表と画面の値がずれた行が、そのまま弱点です。そこだけ直せば、次の問題から精度が上がります。

ずれた行の前後3行だけ読み直す¶

全部やり直す必要はありません。原因はたいてい、境界の + 1 か、条件の不等号の向きです。

見つけたら、同じ型の問題をもう1問だけ解いてみてください。1問で定着します。

まとめ¶

科目Bの探索問題は、覚える量が少ない分野です。差がつくのは、範囲を目に見える形にできているかどうかだけです。

今日の流れを、もう一度振り返っておきましょう。

この5段は、探索以外の擬似言語問題にもそのまま使えます。変わるのは表の列の名前だけです。

最初は表を書くのが遠回りに感じるかもしれません。それでも3問ほど解けば、書く量が自然に減っていきます。

範囲の動きが見えるようになれば、探索問題は短時間で確実に取れる分野に変わります。今日のうちに1問、表を書きながら追ってみてください。

一度その感覚をつかめば、初めて見るコードでも落ち着いて読めるようになります。焦らず、1行ずつでいきましょう。