武蔵野個別指導塾の特徴

高校情報I 線形探索—見つからない場合と重複がある場合の出力を設計する｜武蔵野個別指導塾

公開 2026.11.14更新 2026.11.14武蔵野個別指導塾の特徴情報I コンピュータとプログラミングを掘り下げる

備品番号を先頭から比較し、重複時の位置と未発見の返り値を設計するのが線形探索です。

よくあるのは、高校生が備品番号を探し、一致する番号がないのに最後の位置を答えてしまう場面です。最後に調べた位置と、探す番号が見つかった位置は同じ意味ではありません。一覧が空の場合も含め、どの時点で何を返すかを決めてから手順を作ります。

要点（結論から）

先頭から順に比べ、最初の一致で位置を返します。
未発見の -1 と最後に調べた位置を区別します。
空一覧では比較回数は0、重複時は返す一致を先に決めます。

位置を答える前に決めること

線形探索は、一覧の要素を先頭から順に調べる方法です。問題には、処理を追って返り値を求める型、条件に合うように探索を作る型、誤った返り値の原因を探す型があります。いずれも、どの要素を調べたかと、何を返すかを分けて読みます。

ここでは備品番号を整数のリストに入れます。位置は先頭を0とし、要素数が n のとき0から n − 1までです。リストは空でもよく、番号が重複していても構いません。探す番号と等しい要素が複数あれば最初の位置を返し、一致がなければ -1 を返します。位置と比較回数を、この順の組で出力します。比較回数は、一覧の要素と探す番号との等しいかどうかの比較を行った回数です。入力の型を調べる処理や、繰り返しを続けるかの判定は数えません。

リスト内の番号も探す番号も整数とします。それ以外は入力の誤りとして扱い、未発見の -1 とは区別します。正常な入力に対する未発見は探索の結果ですが、壊れた入力から探索結果を作ることはできません。ここでは整数を識別するため、真偽値も整数の番号としては受け付けないことにします。

調査済みの範囲を伸ばす

図1のように、現在の位置より前を調査済みと考えます。最初の一致を返す手順では、次の比較に進む時点で調査済みの範囲に一致はありません。まだ調べていない範囲に一致があるかは、比較するまで決められません。

図1では先頭から2要素を調べ、次に位置2を調べます。仮に位置2で一致すれば、それより前は一致しなかったため、位置2が最初の一致です。一覧を最後まで調べて一致しなければ、未発見と判断できます。昇順などの並びを前提としないため、途中で大小関係から残りを省くことはしません。

正しさを3段階で見ます。開始前は調査済みの範囲が空なので、そこに一致はありません。比較して不一致なら、その位置を調査済みに加えても、一致がないという条件は保たれます。一致なら、その前に一致がないことから最初の位置を返せます。最後まで不一致なら、一覧全体に一致がないので -1 を返せます。空の一覧でも、比較を行わず全体に一致がないと判断します。

繰り返しは位置を0から順に1ずつ進め、要素数の手前で終わります。一致した場合はその場で終了するため、要素数が有限なら必ず止まります。成功した例を何件か動かすことは実装の検査になりますが、あらゆる入力で正しい理由は、この調査済み範囲の性質と終了条件から説明します。

備品番号を1つ探す

備品番号の一覧を [34, 17, 52, 17, 41]、探す番号を17とします。位置は0から始まり、最初の一致の位置と比較回数を組で答えます。手でたどると位置0の34は不一致、位置1の17は一致です。期待値は (1, 2) です。位置3にも17はありますが、最初の一致を求めるので比較しません。

図2のように、比較した2要素と、その後に残る未調査の要素を分けると、重複があっても返す位置が定まります。図2の数値は、この備品一覧と同じです。

次の自作プログラムでは、search が位置と比較回数を返します。呼び出し側の print は、返された組を表示します。

def search(items, target):
    if type(items) is not list or any(type(x) is not int for x in items) or type(target) is not int:
        raise ValueError('整数の一覧と整数を指定')
    count = 0
    for i in range(len(items)):
        count += 1
        if items[i] == target:
            return i, count
    return -1, count

print(search([34, 17, 52, 17, 41], 17))

最初の行は、一覧と探す番号を受け取る関数を定義します。次の条件はリストであること、要素が整数であること、探す番号が整数であることを確かめます。条件に合わなければ ValueError を発生させ、誤ったデータを未発見と混同しません。count は比較前の0から始めます。

range は位置0から最後の位置までを順に渡します。各回で count を1増やしてから、その位置の要素を target と比べます。一致すれば return で位置と回数を返し、関数を終えます。不一致なら次の位置へ進みます。繰り返しが終了するまで返らなかった場合に限り、最後の行が -1 と回数を返します。

比較前の位置  比べる番号  判定      比較後の回数
0             34          不一致    1
1             17          一致      2

Python 3.14.8 で上記の入力を実行した結果は (1, 2) で、手で求めた期待値に一致しました。位置1の値が17であり、前の位置0は34なので、位置だけでなく最初の一致という条件にも戻して確かめられます。

末尾と未発見を区別する

同じ一覧で41を探すと、34、17、52、17、41の順に5回比較して (4, 5) です。位置4には41があり、その前には41がありません。一方、60を探すと5回とも不一致です。最後に見た位置は4でも、答えは (-1, 5) です。比較した事実から一致した事実を作ってはいけません。

同じ search を用い、次の6件を発見する場合の検査とします。入力は一覧と探す番号、期待と実際は位置と比較回数です。Python 3.14.8 で実行し、各行で期待と実際が一致しました。

一覧                   番号  期待        実際
[34, 17, 52, 17, 41]   17    (1, 2)      (1, 2)
[34, 17, 52, 17, 41]   34    (0, 1)      (0, 1)
[34, 17, 52, 17, 41]   41    (4, 5)      (4, 5)
[17]                   17    (0, 1)      (0, 1)
[6, 17, 17]            17    (1, 2)      (1, 2)
[8, 3, 12]             12    (2, 3)      (2, 3)

先頭で見つかると1回、末尾まで探すと要素数と同じ回数です。単一要素の一致も先頭の一致です。重複の行では位置1と位置2がともに17ですが、位置1で止めるという指定に合っています。各行の返された位置に戻ると探す番号と一致し、その前には一致がありません。

見つからない場合と入力の失敗を試す

発見する場合と同数の6件を、未発見や処理の失敗について検査します。空一覧と不一致は正常な入力に対する未発見です。残る4件は検索結果を返さない失敗です。外部から一覧を読む処理は環境に依存するため、ここではその代役を渡して失敗を再現します。実際の通信やファイル読込を行ったという意味ではありません。

def from_loader(loader, target):
    return search(loader(), target)

この関数は loader を呼んで一覧を受け取り、search に渡します。loader 自体が例外を出した場合は search に進まず、その例外を呼び出し元に伝えます。ここでは時間切れを検出する仕組みを作るのではなく、読込側が TimeoutError を出す場合の受け渡しを検査します。呼び出し側は例外の種類に応じて再試行や入力の修正を判断でき、失敗を -1 と誤認しません。

各行は独立した入力です。期待と実際の表記は、戻り値か、発生した例外の種類とメッセージです。例外を発生させる代役は、示した種類と文をそのまま送出する関数です。Python 3.14.8 で6件を実行しました。

入力または読込側の動作             期待                      実際
空一覧、番号7                      (-1, 0)                   (-1, 0)
備品一覧、番号60                   (-1, 5)                   (-1, 5)
[1, '破損']、番号1                 ValueError: 整数の一覧と整数を指定
                                                               同じ例外と文
読込側が時間切れを通知             TimeoutError: 時間切れ    同じ例外と文
読込側が読込失敗を通知             OSError: 読込失敗         同じ例外と文
読込側が形式不正を通知             ValueError: 形式不正      同じ例外と文

空一覧は比較対象がなく回数0、60の行は全5要素を見ても一致しないので回数5です。壊れた一覧は先頭に1があっても、全要素の型を先に調べる仕様により例外です。読込側の例外も、位置や比較回数には変換しません。これらの試験は実際に通知された例外を受け渡す確認であり、外部装置の故障や時間制限の仕組み自体を検証したものではありません。

一覧の型と全要素を事前に検査するので、先頭で一致する場合でも型検査は末尾まで行われます。表の比較回数は番号同士の等値比較のみで、型検査を含む処理全体の作業量ではありません。比較回数だけから実行時間を断定しないようにします。

発展: 一致する位置を全部集める

最初の1件ではなく、備品番号9の位置を全部求めるとします。一覧は [9, 4, 9, 2, 9]、位置は0から、出力は位置のリストと比較回数の組です。整数リストと整数が渡されることを前提とし、空一覧も受け付けます。ここでは入力型の検査は呼び出し前に済ませておくとします。

def all_matches(items, target):
    positions = []
    count = 0
    for i in range(len(items)):
        count += 1
        if items[i] == target:
            positions.append(i)
    return positions, count

print(all_matches([9, 4, 9, 2, 9], 9))

positions は発見した位置を入れる空リスト、count は比較回数です。各位置で回数を増やし、一致すれば append でその位置を末尾に加えます。最初の一致で return すると後の一致を失うため、返すのは反復が終わった後です。不一致では位置を加えず次へ進みます。位置は順に調べるので、結果の位置も小さい順に並びます。

手で調べると位置0、2、4が一致し、5要素すべてを比較するため期待は ([0, 2, 4], 5) です。Python 3.14.8 の実際の出力も同じでした。返された各位置の値は9で、残る位置1と3はそれぞれ4と2です。一致する位置の漏れがないことも元の一覧に戻して確認できます。未発見の場合は空リストと比較回数を返し、空一覧では ([], 0) になります。

末尾を誤って返す処理を直す

次の誤った関数は、調べるたびに position を更新します。入力は先ほどの備品一覧と番号60です。期待値は未発見を表す -1 ですが、実際は4になります。

def bad(items, target):
    position = -1
    for i in range(len(items)):
        position = i
        if items[i] == target:
            break
    return position

print(bad([34, 17, 52, 17, 41], 60))

Python 3.14.8 での実際の出力は 4 です。図3のように、最後の比較も不一致なのに position は4に更新されます。break が実行されなかったことを返り値に反映していないため、最後に見た位置が結果に残ります。

図3の修正では、一致したときに限ってその位置を返し、最後まで一致しなければ -1 を返します。上の search はこの修正に比較回数を加えたものです。同じ入力を再実行すると (-1, 5) で、位置だけなら -1 です。さらに末尾の41では (4, 5)、先頭の34では (0, 1) となり、未発見への修正が発見時の返り値を壊していないことも確かめました。

空一覧だけで誤りを試すと、誤った関数も初期値 -1 を返すため欠陥を見逃します。非空で未発見の入力と、実際に末尾で見つかる入力を対にして、同じ位置4が片方だけに返ることを確かめます。

自分でたどる5問

以下は整数の備品番号の一覧です。位置は0から始め、比較回数は要素と探す番号の等値比較の回数です。1から4は最初の一致の位置と比較回数を組で、未発見は位置 -1 として答えてください。5は一致する位置のリストと比較回数を組で答えてください。いずれも空一覧を認めます。

[7, 2, 5, 2] から2を探します。
[11, 4, 6] から8を探します。
空一覧から3を探します。
[20, 13, 8, 5] から5を探します。
[7, 2, 5, 2] から2と一致する位置を全部探します。

答えと位置への戻し方

(1, 2) です。位置0の7は不一致、位置1の2は一致です。位置3も2ですが、位置1が先なので、そこで止めます。返した位置1の値と探す番号が一致することも確認します。
(-1, 3) です。11、4、6の3要素を調べても8はありません。末尾の位置2は調べた位置であって、一致した位置ではありません。
(-1, 0) です。要素がないので比較もなく、該当する位置もありません。位置0を参照しようとしないことが大切です。
(3, 4) です。20、13、8はいずれも不一致で、4回目に位置3の5と一致します。位置3の値は5で、前の3要素に5はありません。
([1, 3], 4) です。4位置を最後まで比較し、位置1と3を順に記録します。返した両位置は2で、残りの位置0と2は7と5です。

Python 3.14.8 で、それぞれ search または all_matches に指定の一覧と番号を渡した実際の出力も、順に (1, 2)、(-1, 3)、(-1, 0)、(3, 4)、([1, 3], 4) でした。手で出した答えと元の一覧を、実行値と合わせて照合しています。