
武蔵野個別指導塾の特徴
共通テスト情報I 線形探索の停止位置—見つかった後も続けたとき最後に残る位置を読む|武蔵野個別指導塾

音符番号の重複を左からたどり、停止の有無で変わる位置を表と反例で読みます。鍵は上書きです。
よくあるのは、高校生が楽譜に付けた音符番号を左から探し、最初に見つけた場所を答えたのに、処理の出力は別の場所になる場面です。同じ番号が後にもあれば、発見後の命令によって保存された位置が変わることがあります。見つかった瞬間だけでなく、その後に何を調べ、いつ結果を出すかまで読む必要があります。
ここで使う音符番号や列は、説明のために作った条件です。音の高さや楽譜の読み方は問いません。番号の一致を使って、保存された位置がどのように変わるかを確かめます。
出力まで追う問いの型
1つ目は、同じ番号が複数ある列を左から最後まで調べ、出力される添字を求める型です。一致するたびに位置を保存するなら、後の一致で前の記録が上書きされます。最初の一致を見つけたところで追跡を終えると、出力時点の値を見落とします。
2つ目は、同じ列で一致した直後に反復を抜ける処理と、最後まで続ける処理を比べる型です。異なるのは停止の有無だけであり、一致が1回なら結果が同じでも、重複があると差が現れます。同じ答えになった一例だけで、2つの処理がいつも同じとは言えません。
3つ目は、探す番号がない列や空の列について、初期値の意味を問う型です。位置を保存する変数が更新されなければ、初めに入れた印がそのまま出力されます。印を有効な添字と区別していなければ、未発見と発見を結果だけで見分けられません。
位置の記録はいつ変わるか
線形探索は、要素を順に調べて目的の値と比べる方法です。ここでは左端から右端へ進みます。列の要素そのものが音符番号、添字がその要素の位置です。Pythonでは左端の添字を0とし、要素数が4なら有効な添字は0から3です。番号と添字がたまたま同じ数でも、役割は異なります。
保存する変数を pos、調べる位置を i、探す番号を target とします。pos の初期値は -1 とし、未発見の印にします。この処理では -1 を配列の添字として使わず、結果として出力する印に限ります。Pythonには負の添字という別の使い方がありますが、ここでは対象にしません。
図1のように、各位置で番号が一致したときだけ pos に現在の i を入れます。不一致なら直前の pos が残ります。次の位置へ進むことと、保存した位置が変わることは別の出来事です。

調べ終えた範囲に一致があれば、pos はその範囲内で最後に一致した位置です。最初は調べた範囲が空なので -1 です。不一致では最後の一致は変わらず、一致では現在の位置がそれまでで最も右の一致になります。この関係が各回で保たれるため、右端まで調べた後には列全体の最後の一致が残ります。
出力が位置ではなく番号そのものだと読み違えると、たまたま同じ数字の例では誤りに気づきにくくなります。そこで、保存する右辺が notes[i] なのか i なのかも確認します。前者なら番号、後者なら位置です。位置を答える場合は、出力された整数を添字として元の列に戻し、その要素が対象と一致するか、さらに右側に一致が残っていないかを別々に調べます。
この結論には条件があります。左から右へ順に最後まで調べ、一致のたびに現在位置を書き込み、不一致では保存値を変えないことです。逆向きに調べれば最後に書き込む位置の意味も変わります。停止命令が途中にあれば、その後の位置は調べません。
基本例題:音符番号を最後まで探す
番号の列を [4, 7, 4, 9, 4]、探す番号を 4 とします。添字は左端から0で始まり、右端の4までを含めて調べます。次の自作プログラムが、反復終了後に出力する整数を求めてください。
notes = [4, 7, 4, 9, 4]
target = 4
pos = -1
for i in range(len(notes)):
if notes[i] == target:
pos = i
print(pos)
notes は番号の列です。range(len(notes)) はこの列では0から4までを順に渡し、5は渡しません。== は左右が等しいかの判定で、pos = i は位置の保存です。print は反復の外にあるので、途中ではなく全位置を調べ終えてから1回だけ出力します。
初期状態では pos は -1 です。下の各行の保存後の値は、その位置の条件判定と、真の場合の代入を終えた時点のものです。
| i | 調べた番号 | 4と一致 | 保存前 | 保存後 |
|---|---|---|---|---|
| 0 | 4 | 真 | -1 | 0 |
| 1 | 7 | 偽 | 0 | 0 |
| 2 | 4 | 真 | 0 | 2 |
| 3 | 9 | 偽 | 2 | 2 |
| 4 | 4 | 真 | 2 | 4 |
最初の位置で真になり0を保存します。次の7は一致しないため、代入文を実行せず0を保ちます。添字2では再び真なので2へ上書きし、添字3ではその2を保ちます。最後の添字4でも真となり、保存値は4になります。次に渡す添字はなく、反復が終わってから 4 が出力されます。
図2のように、保存値は -1、0、2、4と変わります。出力の4は探した番号と同じ数字ですが、答えの意味は音符番号ではなく添字です。列の添字4には実際に番号4があり、その右に要素はないので、最後の一致という目的にも合います。

もし先頭の一致で停止したら0ですが、元の処理にはその命令がありません。途中で答えを確定せず、反復の後に置かれた出力までたどることが必要です。
標準例題:停止命令を加える
同じ列 [4, 7, 4, 9, 4] と対象4を使い、基本例の pos = i の直後に、同じ字下げで break を加えます。反復を抜けた後の出力は整数で何になりますか。また、元の処理との差を説明してください。
最初の添字0で一致して pos は0になります。直後の break により、その for の反復を抜けます。添字1以降の判定は行わず、反復後の print は0を出力します。元の処理は最後まで調べるので4です。どちらも一致位置を出しますが、前者は最初、後者は最後の位置を選びます。
停止命令の有無だけを変えた比較です。例えば対象を7に変えれば一致は添字1の1回なので、両方とも1を出します。結果が同じ理由は、停止後に別の一致がないからです。処理が同じになったわけではなく、最後まで続ける側は残りの位置も判定します。
発展例題:答えが一致する条件
長さが0以上の整数の列を左から右へ調べるとします。基本例の最後まで上書きする処理と、標準例の最初の一致で止める処理は、ともに未発見の印を -1 とします。2つの出力が一致するのはどのようなときでしょうか。出力を整数として考えます。
一致が0回なら、どちらも一度も保存値を変えず -1 を出します。空の列もここに含まれます。一致が1回なら、その唯一の位置を両方が保存します。一致が2回以上なら、左から調べるため最初の一致位置と最後の一致位置は異なります。したがって、出力が一致する条件は一致が高々1回であることです。
たとえば [8] から8を探すと両方とも0です。一方、対象が6なら両方とも -1 です。いずれも右端までの範囲を考えた結果で、-1を実在する位置として扱ってはいません。空の列では range(0) が空なので判定自体がなく、初期値が出力されます。
この判定は、未発見の印が有効な添字と重ならないという約束にも依存します。仮に印を0にすると、先頭で見つかった場合と未発見の場合がともに0となり、結果から区別できません。目的が位置を返すことなら、位置の選び方だけでなく、見つからなかった場合の表現も仕様の一部です。
誤答の最初のずれを直す
基本例で「最初に4を見つけたので出力は0」とする誤答を考えます。添字0を処理した直後の保存値としては0で正しいのですが、出力はその時点では行われません。図3のように、添字2の一致を処理した直後に、0のままという追跡と実際の値2が初めて食い違います。

| 時点 | 誤った追跡 | 実際の保存値 | 原因 |
|---|---|---|---|
| 添字0の処理後 | 0 | 0 | この時点では一致 |
| 添字2の処理後 | 0 | 2 | 2回目の一致を無視 |
| 添字4の処理後 | 0 | 4 | 最後の一致も無視 |
修正するときは、まず停止命令があるか、出力が反復の内側か外側かを確認します。元の処理を読む問題なら、停止命令を勝手に補わず、一致ごとに保存欄を書き換えます。最初の位置が必要な目的に処理を変更する問題なら、一致して保存した直後に break を置く方法があります。目的が最後の位置なら、それを加えると誤りです。
反例は短くできます。列 [3, 3] で3を探すと、最後まで続ける版は0を保存した後に1へ上書きし、1を出します。停止版は0を出します。1要素では2つの一致を置けないので、この違いを示すには2要素が最小です。列中の両方が対象であることを確かめれば、単に異なる数が出たというだけでなく、どちらの位置を選んだかも確認できます。
練習:位置と未発見を区別する
次の5問の数値と場面は練習用に作ったものです。いずれも添字は左端を0とし、右端まで順に調べます。最後まで続ける版は pos を -1 にして一致のたびに現在の添字を保存し、反復後に出力します。停止版は保存の直後に break を実行します。答えは指定された整数で示してください。
- 展示札の列
[12, 15, 12, 16]から12を探すとき、最後まで続ける版の出力を求めてください。 - 部品番号の列
[21, 22, 21, 21]から21を探すとき、停止版と最後まで続ける版の出力をこの順に求めてください。 - 座席記号を整数で表した列
[31, 32, 33]から34を探すとき、両版の出力を求めてください。 - 空の箱番号の列
[]から41を探すとき、両版の出力と判定回数を求めてください。 - 標識番号の列
[51]から51を探す場合と52を探す場合について、最後まで続ける版の出力をそれぞれ求めてください。
練習の答えと道筋
-
答えは2です。添字0で0を保存し、添字1は不一致、添字2で2に更新し、添字3は不一致です。列の添字2は12で、その右の16は12ではありません。したがって2は最後の札の位置として条件を満たします。
-
答えは順に0、3です。停止版は先頭で0を保存して抜けます。続ける版は0、2、3の順に保存し、最後に3を出します。添字0と3の部品番号はいずれも21で、先頭より前や末尾より後には要素がありません。
-
両方とも -1 です。31、32、33のいずれも34ではないので、保存は一度も起きません。最後まで続ける版は3回判定し、停止版も一致がないため3回判定します。-1は座席の位置ではなく、見つからなかった印です。
-
両方とも出力は -1、判定回数は0です。調べる位置がないため一致の判定も保存も起きません。空の箱番号の列に41を指す位置が存在しないことと、未発見の印が残ることが対応します。
-
51を探す場合は0、52を探す場合は -1 です。前者は添字0で一致し、後者は同じ位置で不一致です。唯一の要素は51なので、0は存在する位置、-1は位置が存在しないことを表します。
覚えておきたいこと
左から最後まで調べて一致ごとに上書きすると、最後の一致位置が残ります。
一致直後に停止すれば、最初の一致位置が残ります。
未発見の印と有効な添字を区別し、出力する時点まで追います。
追跡表のどこを見直すか
お子さまが最初の位置を答えた場合、まず表の「保存後」の列を一致ごとに更新したかを確かめます。2回目の一致の行で値が変わっていなければ、条件の真偽か代入の実行を見直します。一方、表の最後の値は正しいのに答えが違うなら、出力の位置を取り違えていないか確認できます。
個別指導では、重複する列と一致が1回の列を並べ、どの行から2つの処理の経路が分かれるか説明してもらいます。空の列や未発見でも初期値を指せるかを確かめると、位置と印の混同も見つかります。保存値は、最後に実行された一致時の代入が決めます。
もう「日東駒専」を目標にしないでください。
武蔵境駅徒歩30秒、講師1人に生徒1人の完全1対1。授業のあいだ、先生は隣を離れません。いまの詰まりを、無料相談でそのまま話してください。
まず15分だけ電話で話したい方は、無料電話相談(15分)から。塾からお電話を差し上げます。
本気になった日が、入塾の日。
お子様の教育、迷ったら「丸投げ」してください。必ず、期待以上の結果で返します。武蔵野で育む、武蔵境で学ぶ。
電話は年中無休。365日、24時間、お電話可能。




