共通テスト情報I 探索と終了条件—見つかった位置と処理を止める時点を追う｜武蔵野個別指導塾

一致した位置と未発見を比較順から区別する鍵は、探索の終了条件です。

よくあるのは、一覧の最後まで目的の値が見つからなかったのに、高校生が最後に調べた位置を答えてしまう場面です。最後に比較した位置は記録できても、そこに目的の値があるとは限りません。逆に同じ値が複数あるときは、最初の一致で止まる処理なのか、最後まで調べる処理なのかを確かめる必要があります。位置の数字だけでなく、その数字が何を表しているかまで追ってみましょう。

問いは位置と停止のどちらにあるか

線形探索は、並んだ要素を端から順に比較して目的の値を探す方法です。ここでは探索用の値を末尾に追加する番兵を使いません。配列の範囲を確かめ、実際にある要素とだけ比較します。途中で見つかった場合と、最後まで調べて見つからなかった場合の出力を分けます。

出方の型は3つあります。1つ目は、比較した位置と値を順に並べ、初めて一致した位置を答える型です。2つ目は、未発見のときに繰返しがどの条件で終わり、何が出力されるかを答える型です。3つ目は、重複や空の配列を含む入力を使い、処理を止める条件の変更が結果にどう影響するかを判定する型です。

問題によって、位置を0から数えるか1から数えるか、未発見を何で表すかは変わります。知っている別の書き方を持ち込まず、その問題で定義された規則を最初に書き出します。探索を高速化する別の方法や並べ替えの手順には広げず、比較の順序と停止後の出力に注目します。

調べる位置と答える位置を分ける

図1のように、調べる位置が範囲内にあることを確かめてから、そこにある値を目標と比較します。範囲外なら要素を読まずに未発見へ進みます。範囲内で一致すればその位置を答え、不一致なら位置を1つ進めて再び範囲を確かめます。

この図1の矢印は判断の順序を表します。範囲確認を先に置くのは、存在しない位置を読まないためです。一致で停止するため、その後に同じ値があっても比較しません。未発見と判定できるのは、対象となる位置を順にすべて調べ終えた後です。

「要素」は配列に並ぶ値、「添字」はその要素の位置を示す番号です。例えば添字を1から数える3個の配列では、調べられる位置は1、2、3です。位置4は最後の位置ではなく、範囲の外を示します。添字を0から数える問題では別の範囲になるため、先頭の番号と要素数の両方を確認します。

次の自作記法では、← は右側の値を左側の変数に代入します。「等しい」は値の比較であり、代入ではありません。条件が成り立つ間、繰返しの中を上から順に実行し、一致したらその繰返しを直ちに抜けます。整数除算や剰余は使いません。配列Aは先頭を1番とし、要素数をnとします。nは0以上の整数で、nが0なら要素はありません。目標と要素は整数です。

位置 ← 1
答え ← -1
位置がn以下の間、繰り返す
    Aの位置番目が目標と等しければ
        答え ← 位置
        繰返しを抜ける
    位置 ← 位置を1増やした値
答えを出力する

答えの初期値である-1は、この問題で決めた「未発見」の印です。実在する添字1からnとは区別できます。一致時にだけ答えを書き換えるので、不一致のまま位置が進んでも、答えは-1のままです。変数「位置」は次に調べる場所を管理し、「答え」は出力する結果を保持します。両者は同じ変数ではありません。

基本例題：途中で初めて一致する

配列Aの値が先頭から [8, 4, 7, 4]、目標が4、要素数が4のとき、上の処理を実行します。出力される整数と、実際に比較した位置を順に答えてください。添字は1から始まり、未発見なら-1を出力します。

初期状態は位置が1、答えが-1です。位置1は4以下なので、Aの1番目の8と目標4を比べます。一致しないため、答えは-1のまま、位置を2に進めます。次に位置2も範囲内です。Aの2番目の4は目標と等しいので、答えに2を代入して繰返しを抜けます。

図2の追跡表では、比較した2行だけを示しています。最後の列はその行の判断後に保持される答えです。位置3や位置4の値は配列に存在しますが、この実行では比較されません。

図2のように、出力は整数2、比較した位置は順に1、2です。答えを元の配列に戻すと、2番目の値は確かに4です。さらに先頭の8は4ではないので、2は最初に一致した位置です。4番目にも4がありますが、2番目で抜けるため、4番目は答えにも比較した位置にも入りません。

処理を1行ずつ見ると、一致した行では「位置を1増やす」行に進みません。繰返しを抜けた後に出力があるからです。したがって、停止直後の位置も2、答えも2です。この例では2つの数が偶然そろいますが、未発見の場合にはそろいません。答えが位置と常に同じだと覚えると、次の例で誤ります。

比較した回数も問われたら、条件判定の回数と値の比較回数を混同しないようにします。この例で値の比較は2回です。位置が範囲内かを調べる判定も、位置1と2で行いますが、別の問いとして数えます。停止後に位置3について範囲確認を行うことはありません。

少し難しい例題：最後まで探しても見つからない

同じ処理に、先頭から [6, 1, 9] の配列と目標5を与えます。要素数は3です。出力される整数、比較した位置、停止直後の位置を答えてください。位置は1から始まり、未発見を-1とします。

初期状態は位置1、答え-1です。位置1の6は5と異なるので位置2へ進みます。位置2の1も異なるので位置3へ進みます。位置3の9も異なるので、位置を4にします。ここで「位置が3以下」は成り立たず、繰返しが終わります。位置4の要素を読む処理は実行されません。

したがって出力は-1、比較した位置は順に1、2、3、停止直後の位置は4です。元の配列の6、1、9を照合すると、いずれも5ではありません。最後に比較した位置3が実在することと、そこが一致した位置であることは別です。答えが-1のままなのは、答えを書き換える一致の行が一度も実行されなかったからです。

境界を変えて、要素数が0の空の配列でも考えます。初期位置1は0以下ではないため、値の比較は0回で、答え-1が出力されます。停止直後の位置は1です。最後の要素は存在しないため、最後の値を読もうとする説明は成立しません。この確認は、繰返しが始まる前に条件が偽になる場合を見落とさないために役立ちます。

一方、要素が1個でその値が目標と等しいなら、位置1で一致し、答えは1です。1個で異なるなら、その1個を比較した後に位置が2となり、答えは-1です。空、最小の非空、一致、未発見の違いは、要素を読めるかと答えを書き換えたかで整理できます。

誤答の原因を停止の直前まで戻す

難しい例題で「3を出力する」としたとします。3は最後に比較した位置ですが、Aの3番目は9で、目標5ではありません。最後に調べた位置を、一致した位置と取り違えたことが原因です。図3のように、位置3で不一致だった後の処理をたどれば、出力値を修正できます。

図3では、位置3の値9と目標5が不一致です。位置は4へ進み、範囲外となります。答えは初期値-1から変わらないので、出力は-1です。位置4を答えるのも誤りです。4は次に調べようとして範囲外と判定された位置で、配列の要素を表しません。

もう1つの誤りは、基本例題で4番目にも目標があるため、答えを4にすることです。位置2で一致した直後に繰返しを抜けるので、位置4は調べません。停止の行を飛ばして表を最後まで埋めると、別の処理を解いてしまいます。修正するときは、表の各行に比較結果だけでなく「続けるか、抜けるか」も記してください。

範囲の判定を省く誤りにも注意します。未発見後の位置4を使って要素を読もうとすると、定義された配列の範囲外です。範囲外を勝手に0とみなしたり、実行できたことにしたりはしません。条件を上から確認し、値の比較が実際に行われたかを判定します。

条件を変えたときの読み直し

同じ配列でも、停止の指示が変われば答えは変わります。基本例題の [8, 4, 7, 4] で、仮に一致しても抜けずに最後まで調べ、そのたびに答えを更新する処理なら、位置2で答えが2になった後、位置4で答えが4になります。この説明は条件変更の比較であり、元の処理の答えは2のままです。どの行を変更したかを示さずに「最後の一致」と決めることはできません。

逆に、末尾まで進んだことを未発見の根拠とするには、実際に全要素と目標を比較したことが必要です。途中で回数制限などにより探索を中断した場合、未確認の位置に目標がある可能性が残ります。ここでの処理には時間切れや外部の道具による中断は定義されていません。そのような中断が起きたとしても、それをこの処理の未発見の出力-1と同一視しないでください。

入力の条件も結果の一部です。要素数より短い配列を渡す、整数以外の値を混ぜる、といった壊れた入力の扱いは、この処理では定義していません。実際のプログラムで入力検査や例外処理を加える場合は、異常を知らせる結果と、範囲内を探し終えた未発見を分けて設計します。例外が起きた位置や停止時点は、追加された規則を読まずに推測できません。

自分で追う4問

以下の4問は、用語の節にある同じ処理を使います。各配列は先頭が1番で、目標と要素は整数、未発見の出力は-1です。各問とも、出力を整数で、比較した位置を順に答えてください。比較がないときは「なし」と書きます。停止直後の位置も整数で答えます。

1. 配列 [3, 8, 2]、目標3、要素数3です。
2. 配列 [2, 5, 8]、目標8、要素数3です。
3. 配列 [4, 6, 7]、目標2、要素数3です。
4. 配列は空、目標9、要素数0です。

答えと手順

1. 出力1、比較した位置は1、停止直後の位置は1です。最初の値3が目標と等しく、答えを1にして抜けます。元の配列の1番目が3であることが、答えの確認になります。後の位置は比較しません。
2. 出力3、比較した位置は1、2、3、停止直後の位置は3です。2、5は目標8と異なり、位置3の8で初めて一致します。3番目の値を元の配列で見直すと8で、それより前の2個は8ではありません。最後の位置で見つかった場合も、未発見とは区別できます。
3. 出力-1、比較した位置は1、2、3、停止直後の位置は4です。4、6、7はいずれも2と異なるため、答えは初期値のままです。位置4は範囲外なので比較しません。元の3個を見直しても目標はなく、未発見という出力と一致します。
4. 出力-1、比較した位置はなし、停止直後の位置は1です。開始時の位置1が要素数0以下ではなく、繰返しの中に入りません。元の配列に要素はないため、一致する位置もありません。目標の値を読もうとするのではなく、要素が存在するかを先に判断します。

1と2は一致して止まる場合、3と4は一致せずに終わる場合です。3では最後の比較後に位置を進め、4では比較する前に範囲外と判断します。どちらも出力は-1ですが、比較回数は違います。出力だけが同じでも、経路が同じとは限りません。

手元に残す要点

• 比較前に位置が配列の範囲内か確かめます。
• 最初の一致で抜けるなら、後の重複は調べません。
• 最後に比較した位置と未発見の出力は別です。
• 空の配列では、この処理の比較は0回です。
• 停止直後の位置と答えを別々に記録します。

どの行からやり直すか

位置と答えが混ざるときは、追跡表に「位置」「比較した値」「一致したか」「答え」「次の動作」の列を作ります。初期値を書き、比較が起きた行だけを埋めてください。一致なら抜ける行まで、不一致なら位置を進めた後の範囲確認まで記します。

個別指導で確かめるなら、まず基本例題の位置2で、なぜ位置3へ進まないかを言葉にします。続いて未発見の例で、最後に比較した位置3と出力-1を別々に示せるかを見ます。空の配列で最初の条件が偽になる理由まで説明できれば、停止時点を値の比較と結びつけて読めています。