武蔵野個別指導塾の特徴

高校情報I 探索と整列の比較—同じ入力で操作数を測り前提と効率を説明する｜武蔵野個別指導塾

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

同じ整数列で探索と整列の比較回数を測り、二分探索に必要な事前整列の費用まで区別して検討します。

よくあるのは、高校生が二分探索で中央から調べる回数だけを数え、先に並べ替える手間を見落とすという場面です。探す作業を1回だけ行うのか、同じ一覧を何度も使うのかで、準備を含めた見方は変わります。ここでは自作の整数の一覧を使い、手順の比較回数と交換回数を測ります。

何を同じ条件にして比べるか

問われ方の1つは、同じ一覧と探す値を与え、線形探索と二分探索の比較回数を求める型です。線形探索は元の順序を使えますが、二分探索には昇順の一覧が必要です。したがって、返す添字が指す一覧も異なります。もう1つは、同じ未整列の一覧を選択ソートとバブルソートに渡し、比較と交換をそれぞれ数える型です。3つ目は、要素の順序や探索回数を変えたときに、準備を含む合計がどう変化するかを説明する型です。

共通の約束を先に決めます。添字は0から始まり、要素数をnとすると有効な位置は0からn-1です。空の一覧も認めます。線形探索は元の一覧で最初に一致した位置を返し、二分探索は昇順の一覧で一致した位置を1つ返します。重複時の二分探索はどの一致でもよいことにします。見つからなければどちらも-1を返します。戻り値は位置と比較回数の組です。

探索の要素比較は、調べた要素と目的値の大小や一致を判定することを、調べた要素1個につき1回と数えます。実装上は一致と大小を別々の式で調べますが、それぞれを別回数にはしません。整列の要素比較は2要素の大小判定1回です。交換は異なる位置の2要素を入れ替えた回数で、同じ位置への代入は数えません。添字の範囲確認や代入は比較回数に含めません。この定義は測る尺度であり、実際に必要な命令の回数や実時間をそのまま示すものではありません。

準備と本番を分けて追う

図1のように、元の一覧から線形探索へ進む道と、整列してから二分探索へ進む道を分けます。二分探索の結果の位置は整列後の一覧での位置です。元の位置が必要なら、値と元の位置を組にして保持するなどの設計が別に必要です。

図1の整列を一度行い、同じ並びを複数回の探索に使える場合は、準備の比較と交換を1回分だけ計上します。一覧が変わるたびに作り直すなら、その都度の整列も数えます。どちらの運用かを決めず、二分探索の本体だけを他の方法の全工程と比較すると、異なる作業を比べることになります。

線形探索では、先頭から調べた範囲に目的値がなければ次へ進みます。最初の一致で止まるため、それ以前に一致がないことも保証されます。末尾まで調べて一致がなければ-1です。空なら比較せずに終わります。調べる位置は毎回1増え、有限個の要素を越えないので停止します。

二分探索では、両端を含む探索区間を持ちます。中央が目的値より小さければ、その中央以前は昇順のため候補から除けます。大きければ中央以後を除けます。一致しなければ中央を含まない側へ端を移すので、区間は必ず短くなります。端が交差したとき候補は空で、未発見です。この説明は昇順という前提に依存します。未整列のまま実行すると、存在する値を捨てる可能性があります。

選択ソートは、未確定部分の最小位置を一巡してから先頭と交換します。一巡ごとに確定部分が左から1つ広がります。バブルソートは左から隣同士を比べ、大きい方を右へ送ります。一巡で未確定部分の最大値が右端に到達します。交換がない一巡では残りも昇順なので停止できます。いずれも対象範囲が有限で、一巡ごとに未確定部分が短くなるため終わります。

基本例題: 4枚の番号札

一覧は [8, 3, 6, 1]、探す値は6です。元の一覧での線形探索と、選択ソート後の二分探索について、位置と比較回数を組で答えます。選択ソートの交換回数も求めます。図2のように、線形探索は8、3、6の順に調べるため (2, 3) です。選択ソートは最初に1を選んで8と交換し、[1, 3, 6, 8] にします。残りの巡回では交換が不要です。比較は3回、2回、1回で合計6回、交換は1回です。

図2の整列後、二分探索の最初の範囲は0から3、中央は切り捨てで1です。位置1の3は6より小さいため、次は2から3です。中央2の6が一致し、(2, 2) を返します。準備を含む比較は6回と2回で計8回、さらに交換が1回あります。線形探索の3回と比べる際、この交換を比較1回に勝手に換算しません。

次の4関数を同じ入力で実行します。各関数は渡された一覧を直接書き換えないよう、整列では最初に複製します。返り値の整列結果、比較回数、交換回数の順も固定します。

def linear(a, x):
    count = 0
    for i in range(len(a)):
        count += 1
        if a[i] == x:
            return i, count
    return -1, count

def binary(a, x):
    left = 0
    right = len(a) - 1
    count = 0
    while left <= right:
        mid = (left + right) // 2
        count += 1
        if a[mid] == x:
            return mid, count
        if a[mid] < x:
            left = mid + 1
        else:
            right = mid - 1
    return -1, count

def selection(a):
    a = a[:]
    count = 0
    swaps = 0
    for i in range(len(a)):
        smallest = i
        for j in range(i + 1, len(a)):
            count += 1
            if a[j] < a[smallest]:
                smallest = j
        if smallest != i:
            a[i], a[smallest] = a[smallest], a[i]
            swaps += 1
    return a, count, swaps

def bubble(a):
    a = a[:]
    count = 0
    swaps = 0
    for end in range(len(a) - 1, 0, -1):
        changed = False
        for j in range(end):
            count += 1
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
                swaps += 1
                changed = True
        if not changed:
            break
    return a, count, swaps

linearのcountは0から始め、各位置の判定前に1増やします。一致すればその位置で戻り、反復を終えても戻らなければ-1です。binaryは左右の端とcountを初期化し、区間が残る間、中央を計算して調べます。一致なら戻り、小さければ左端を中央の次へ、それ以外なら右端を中央の前へ移します。反復後の-1は候補が尽きた印です。

selectionのiは未確定部分の先頭です。smallestをそこに置き、jを次の位置から末尾まで進めます。比較のたびcountを増やし、より小さい値なら位置を更新します。一巡の後、位置が違う場合に限って交換とswapsの加算を行います。同値では更新しませんが、交換によって同値の元の順番が保たれる保証はありません。

bubbleのendは未確定部分の右端です。各巡回の初めにchangedを偽に戻し、jとその右隣を比較します。左が大きいときに交換し、交換数とchangedを更新します。等しい値は交換しません。一巡後に交換がなければbreakで終了し、あれば右端を1つ縮めます。最後に一覧と2種類の回数を返します。

実行環境はPython 3.14.8です。上の関数に [8, 3, 6, 1] と6を渡した期待値と実際の出力は、linearが (2, 3)、selectionが ([1, 3, 6, 8], 6, 1)、bubbleが ([1, 3, 6, 8], 6, 5)、その整列結果を渡すbinaryが (2, 2) でした。整列後には元の4個が各1個ずつ残り、隣接する値は昇順です。線形の位置2は元の6、二分の位置2は整列後の6を指します。

順序を変えた比較と繰り返しの費用

標準例題では同じ4個を逆順 [8, 6, 3, 1] にし、6を探します。整列結果と比較・交換の組をそれぞれ答え、探索は位置・比較回数の組で答えます。選択ソートは ([1, 3, 6, 8], 6, 2)、バブルソートは ([1, 3, 6, 8], 6, 6) です。linearは (1, 2)、整列後のbinaryは (2, 2) です。実際の出力もこの通りでした。

選択では最初に8と1を交換し、次に6と3を交換します。残りは交換不要です。バブルでは1巡目に8が右端へ進み3回交換し、2巡目に6が残りの右端へ進み2回、3巡目に3と1を1回交換します。比較は3、2、1回です。どちらの結果にも4個の元の値が残り、順序が整っています。比較回数が同じでも交換回数は異なります。

反対に、最初から [1, 3, 6, 8] なら選択は比較6回、交換0回、バブルは最初の3比較で交換がなく終了します。実行結果もそれぞれ ([1, 3, 6, 8], 6, 0)、([1, 3, 6, 8], 3, 0) です。選択は未確定部分を最後まで調べる設計なので、入力順にかかわらずこの4個では比較が6回です。バブルは早期終了の有無で変わります。別の実装では数え方や停止規則が違うため、回数も変わりえます。

発展例題として、基本例の元の一覧を変えず、6を3回探します。毎回先頭から線形探索する場合と、選択ソートを1回行ってから二分探索を3回行う場合の要素比較と交換を別々に答えます。線形は3回ずつで比較9回、交換0回です。後者は整列6回と探索2回を3回で比較12回、交換1回です。6は毎回存在し、どの返却位置もその時点の一覧の6を指します。回数を変えれば合計も変わるので、この例の結果から常に線形が有利とも断定できません。

たとえば同じ探索を7回なら、線形は比較21回、整列してからの二分は比較20回と交換1回です。比較という尺度では後者が1回少なくなりますが、交換や一覧の複製もあります。実際の時間はデータの置き方や実装などにも左右されるため、この数だけから速さを決めません。既に昇順の一覧があるなら新たな整列は不要ですが、昇順とわかっていることが前提です。

誤答から条件を直す

図3は [7, 2, 5, 2] から9を探す場面です。誤りは、昇順でないまま二分探索に渡し、未発見なら元の末尾の添字3を返す設計です。3は値2の位置であり、9を示しません。未発見と末尾で発見を区別できないことが原因です。

図3の修正では、まず選択ソートで [2, 2, 5, 7] を得ます。比較6回、交換2回です。二分探索は位置1の2、位置2の5、位置3の7を調べ、候補が空になって (-1, 3) を返します。元の一覧で線形探索すれば (-1, 4) です。実際の出力も一致し、どちらの一覧にも9がないことを全要素で照合できます。

前提が壊れた場合も考えます。上のbinaryは昇順を検査する関数ではなく、未整列を渡した場合の答えは保証しません。たとえば [7, 2, 5, 2] で7を探すと、中央の2より右を調べて先頭の7を除いてしまいます。利用側は整列済みを保証するか、別途昇順検査を設けて不正入力を拒否します。検査の比較も費用に加える必要があります。型の異なる値など大小を比較できない入力もこの仕様の対象外で、例外が出たものを未発見の-1に変えてはいけません。

失敗を調べるときは、最終値だけでなく、最初に条件が崩れた位置を表にします。空配列での未発見、単一要素での一致と不一致、重複時の返却位置も再実行します。無制限の待機を避けるため、終了しない疑いのある実装は少数回の追跡に留め、範囲が縮むことを確認してから直します。外部の測定道具が失敗した場合も、測定できなかった回数を0と扱わず、原因を直して再測定します。

練習: 回数と返却位置を分ける

次の5問は上の4関数と同じ約束を使います。探索の答えは位置と比較回数の組、整列の答えは結果の一覧、比較回数、交換回数の組で書いてください。二分探索の入力は昇順とします。

[9, 4, 7] で4を線形探索し、元の一覧を選択ソートしてから4を二分探索します。それぞれの答えと整列結果を求めてください。
[5, 1, 4, 2] を選択ソートとバブルソートで整列します。それぞれの3つの結果を求めてください。
[6, 3, 3, 1] で3を線形探索します。また、この一覧を選択ソートしてから3を二分探索します。各探索の答えと、整列の比較・交換回数を求めてください。
昇順の [2, 4, 6, 8, 10] で7を線形探索と二分探索します。両方の答えを求め、未発見と判断できる理由を述べてください。
空の一覧で4を探す2種類の探索と、空の一覧の2種類の整列について、それぞれの戻り値を答えてください。さらに [4] で9を探す2種類の結果を答えてください。

練習の答えと照合

線形は (1, 2) です。9、4を順に調べ、元の位置1に4があります。選択は ([4, 7, 9], 3, 2) です。最初に9と4、次に9と7を交換します。二分は中央の7、次に4を調べ (0, 2) です。整列後の位置0に4があり、元の3個も残っています。
選択は ([1, 2, 4, 5], 6, 2)、バブルは ([1, 2, 4, 5], 6, 4) です。選択の交換後は順に [1, 5, 4, 2]、[1, 2, 4, 5] です。バブルは最初の巡回で5が右端へ移り3回、次の巡回で4と2を交換して1回です。最後の比較では交換しません。結果の各値は元の札と対応します。
線形は (1, 2) で、先頭の6の次にある3を返します。選択の結果は ([1, 3, 3, 6], 6, 1) です。二分は中央の位置1ですぐ3を見つけ (1, 1) です。もう一方の3も一致ですが、二分探索には最初の一致を返す約束はありません。どちらの返却位置もそれぞれの一覧で3を指します。
線形は (-1, 5)、二分は (-1, 2) です。二分では位置2の6を調べて右側へ進み、位置3の8を調べて右端を2にします。左端3が右端2を越え、候補がなくなります。元の一覧の各値にも7はありません。
空なら両探索は (-1, 0)、両整列は ([], 0, 0) です。調べる要素も交換する位置もありません。[4] で9を探すと両探索とも (-1, 1) です。4は9と異なり、他に候補はありません。[4] で4なら両方 (0, 1) です。これらと問1から4の結果はPython 3.14.8で実行し、記載の期待値と実際の出力が一致しました。手でも各位置と整列後の個数を照合しています。