Coding Interview Prep · レッスン

古典的な二分探索：左、右、中央

Q: 「古典的な二分探索：左、右、中央」レッスンは無料ですか？

はい。「古典的な二分探索：左、右、中央」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Coding Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Coding Interview Prepコースには全4レッスンが含まれています。

Q: Coding Interview Prepを始めるのに経験は必要ですか？

事前経験は必要ありません。CoddyKitのCoding Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン1/4です。

Q: 「古典的な二分探索：左、右、中央」レッスンにはどのくらい時間がかかりますか？

ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。

Q: このCoding Interview Prepレッスンでコードを書いて実行できますか？

はい。すべてのCoding Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。

二分探索を反復版と再帰版で実装し、lo/hi境界のoff-by-oneを正しく扱い、境界ケースの入力で正しさを検証します。

「古典的な二分探索：左、右、中央」はCoddyKit上の無料Coding Interview Prepレッスンです。これはレッスン1/4です。下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。これはCoding Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Coding Interview Prepコースには全4レッスンが含まれています。

二分探索が重要な理由

二分探索は、各ステップで探索範囲を半分にすることで、O(n) の線形探索を O(log n) に削減します。100万個の要素を持つ配列では、線形探索は最大1,000,000回の比較を必要としますが、二分探索では最大20回です。この効率の高さから、二分探索はコーディング面接で最も頻繁に出題されるアルゴリズムの1つです。

核心となる考え方は、ソート済み配列であれば、1回の比較の後に、残りのデータのどちらの半分を完全に捨てられるか判断できることです。

Left・Mid・Rightの枠組み

二分探索では、3つのインデックスポインタを使います。lo（左端の境界）、hi（右端の境界）、mid（中央位置）です。各反復で mid = (lo + hi) // 2 を計算し、target と arr[mid] を比較します。target の方が小さければ hi = mid - 1 として、target の方が大きければ lo = mid + 1 とします。一致すれば見つかったことになります。

ループは lo <= hi の間続きます。target が見つからないままループを終了した場合は、-1 を返します。

def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

print(binary_search([1, 3, 5, 7, 9, 11], 7))  # 3
print(binary_search([1, 3, 5, 7, 9, 11], 6))  # -1

midでの整数オーバーフローを避ける

mid = (lo + hi) // 2 という式は、固定幅整数を使う言語（JavaやC++）では整数オーバーフローを引き起こす可能性があります。Pythonの整数は任意精度なのでオーバーフローは発生しませんが、面接官は安全な代替方法を知っていることを期待しています。それが mid = lo + (hi - lo) // 2 です。

この形式でも同じ中央位置を計算できますが、2つのポインタを先に加算するのではなく、距離の半分だけを lo に加えます。面接でこの点に触れると、低レベルの問題を理解していることを示せます。

# Safe mid calculation (important in Java/C++, good habit in Python too)
lo, hi = 0, 1_000_000_000
mid_unsafe = (lo + hi) // 2   # fine in Python
mid_safe   = lo + (hi - lo) // 2  # same result, no overflow risk
print(mid_unsafe == mid_safe)  # True

包含境界と排他境界

二分探索で特に難しい点の1つは、hi が最後の有効なインデックスを指すのか（包含、hi = len(arr) - 1）、それとも末尾の1つ先を指すのか（排他、hi = len(arr)）を選ぶことです。異なる規約には、それぞれ異なるループ条件と境界の更新方法が必要です。

包含境界では while lo <= hi を使い、hi = mid - 1 と更新します。排他境界では while lo < hi を使い、hi = mid と更新します。規約を混在させることが、二分探索の実装でバグが発生する最も一般的な原因です。

# Exclusive hi variant — useful for bisect-style lower-bound
def search_exclusive(arr, target):
    lo, hi = 0, len(arr)  # hi is one past last
    while lo < hi:          # strictly less than
        mid = lo + (hi - lo) // 2
        if arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid         # NOT mid - 1
    return lo if lo < len(arr) and arr[lo] == target else -1

print(search_exclusive([2, 4, 6, 8, 10], 6))  # 2

再帰的な二分探索

二分探索は、更新した lo と hi の境界をコールスタック経由で渡すことで、再帰的に記述できます。再帰呼び出しのたびに探索範囲が半分になるため、深さは O(log n) です。基本ケースは、lo > hi（見つからない）または arr[mid] == target（見つかった）です。

反復版はスタックフレームのオーバーヘッドを避けられるため、本番コードでは好まれます。一方、ホワイトボードでは再帰版の方が分割統治の構造を明確に伝えられます。

def binary_search_rec(arr, target, lo, hi):
    if lo > hi:
        return -1
    mid = lo + (hi - lo) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search_rec(arr, target, mid + 1, hi)
    else:
        return binary_search_rec(arr, target, lo, mid - 1)

arr = [1, 3, 5, 7, 9, 11]
print(binary_search_rec(arr, 9, 0, len(arr) - 1))  # 4

エッジケース：空配列と要素が1つの配列

堅牢な二分探索は、エッジケースでもクラッシュせずに処理できなければなりません。特に一般的なものは3つあります。空配列ではループが一度も実行されず、正しく -1 が返されます。要素が1つの配列では mid と lo と hi が等しく、1回の比較で十分です。範囲外のtargetでは最終的に lo が hi を超え、-1 が返されます。

面接で追加の質問に進む前に、必ずこれらの入力で実装を検証してください。

def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

print(binary_search([], 5))       # -1  (empty)
print(binary_search([7], 7))      # 0   (single, found)
print(binary_search([7], 3))      # -1  (single, not found)
print(binary_search([1,3,5], 0))  # -1  (below range)
print(binary_search([1,3,5], 9))  # -1  (above range)

時間計算量と空間計算量

二分探索の時間計算量は O(log n) です。各比較によって探索範囲が半分になるためです。k 回の比較の後に残る範囲は n/2^k であり、これが1になると探索が終了するため、k = log₂ n となります。

空間計算量は、反復版ではO(1)です（3つの整数変数だけを使います）。再帰版では、コールスタックの深さによりO(log n)です。面接では常に両方を述べ、空間が制約される場合は反復版を優先してください。

import math

for n in [10, 100, 1000, 1_000_000, 1_000_000_000]:
    steps = math.ceil(math.log2(n + 1))
    print(f'n={n:>12,}  max comparisons={steps}')

完全一致と境界の探索

古典的な二分探索は、target が存在する位置を任意に1つ返します。しかし、多くの面接問題ではtargetの最初または最後の出現位置が求められます。その場合は、一致が見つかった後も探索を続けなければなりません。すぐに返すのではなく、境界を狭めて探索を続けます。

最初の出現位置を探す場合、arr[mid] == target が見つかったら mid を候補として記録し、hi = mid - 1 とします。最後の出現位置を探す場合は、lo = mid + 1 とします。

def first_occurrence(arr, target):
    lo, hi, result = 0, len(arr) - 1, -1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] == target:
            result = mid
            hi = mid - 1   # keep searching left
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return result

print(first_occurrence([1, 2, 2, 2, 3], 2))  # 1

Pythonのbisectモジュールを使う

Pythonの標準ライブラリには、本番環境で使える二分探索として bisect.bisect_left(arr, x) と bisect.bisect_right(arr, x) が用意されています。bisect_left は、配列をソート済みのまま保てる挿入位置のうち最も左のインデックスを返します。つまり、arr[i] >= x となる最初の位置を実質的に求めます。

面接官が bisect の使用を許可する場合もありますが、必ず最初に確認してください。内部でどのように動作するか（O(log n) の二分探索であること）を知っておくことも重要です。

import bisect

arr = [1, 2, 2, 2, 3, 5]

print(bisect.bisect_left(arr, 2))   # 1  (first 2)
print(bisect.bisect_right(arr, 2))  # 4  (after last 2)

# Check if target exists
target = 3
idx = bisect.bisect_left(arr, target)
print(idx < len(arr) and arr[idx] == target)  # True

二分探索でよくある落とし穴

面接で二分探索のバグを引き起こす主なミスは3つあります。1つ目は誤ったループ条件です。包含境界で <= の代わりに < を使うと、最後に残った要素を飛ばしてしまいます。2つ目は不正な境界更新です。+1 や -1 を付け忘れると、lo == hi のときに無限ループが発生します。3つ目はソートされていない配列を対象にすることです。二分探索が正しく動作するのは、ソート済みのデータだけです。

二分探索を書く前に、声に出して次のように確認してください。「配列はソート済みで、境界は包含的であり、ループは lo <= hi の間実行します。」

# BUG: infinite loop when lo == hi because hi = mid never moves past lo
def buggy(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo < hi:              # should be lo <= hi for exact-match
        mid = lo + (hi - lo) // 2
        if arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid            # stops, but never returns mid when found
    return lo if arr[lo] == target else -1

print(buggy([1, 3, 5, 7], 7))  # 3 (works here by luck)
print(buggy([1, 3, 5, 7], 1))  # 0 (correct)
print(buggy([1, 3, 5, 7], 4))  # -1 (correct)

二分探索の面接対策

ソート済み配列、単調増加する関数、または半分に分割できる探索範囲が問題に登場したら、すぐに二分探索を検討してください。面接では、次のように考えを説明します。「配列はソート済みなので、比較ごとに要素の半分を捨てられ、O(log n) になります。」

少なくとも3つの入力、つまり先頭の値、末尾の値、存在しない値で解を必ず検証してください。聞かれる前に「時間計算量は O(log n)、空間計算量は O(1) です」と明確に述べると、基礎がしっかりしていることを示せます。

理解度チェック

このレッスンで扱った Data Structures & Algorithms — Coding Interview Prep の概念について、理解度を確認しましょう。

レッスンのまとめ

このレッスンでは、二分探索は各ステップで探索範囲を半分にするため、時間計算量 O(log n) であること、包含境界の規約では lo <= hi を使い、lo = mid+1 および hi = mid-1 と更新すること、そして最初または最後の出現位置を見つけるには、一致した時点ですぐに返さず、探索を続けることを学びました。次は、二分探索を回転配列やソートされていない配列に応用する方法を探ります。

よくある質問