DSA Interview Prep · レッスン

答えの範囲に対する二分探索

Q: 「答えの範囲に対する二分探索」レッスンは無料ですか？

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

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

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

Q: 「答えの範囲に対する二分探索」レッスンにはどのくらい時間がかかりますか？

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

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

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

連続した答えの範囲を探索空間として扱い、minimum-time-to-complete-jobsやcapacity-to-ship-packagesのような問題を解きます。

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

答え空間の二分探索

多くの人は、ソート済み配列から値を探すための二分探索を知っています。しかし二分探索は、答えの候補空間に適用するとさらに強力です。配列を探索する代わりに、数値の範囲を探索します。たとえば「すべての荷物を配送するのに必要な最小日数はいくつか」といった問題で、確認関数を使って候補の答えが実現可能かどうかを判断します。

この手法により、多くの最適化問題の計算量をO(n²)以上からO(n log(max_answer))に改善できます。

答え空間のテンプレート

テンプレートは3つの要素で構成されます。まず、すべての有効な答えを含む探索範囲[lo, hi]を定義します。次に、midの値が実現可能ならTrueを返す実現可能性チェックcan_achieve(mid)を作成します。最後に[lo, hi]に対して二分探索を行います。can_achieve(mid)がTrueなら、より小さい（または大きい）答えの方向へ進み、そうでなければ反対方向へ進みます。

重要なのは、実現可能性関数が単調でなければならないことです。つまり、ある答えが実現可能なら、それより先のすべての値も実現可能になる（または、それより小さいすべての値が実現不可能になる）必要があります。

# Generic template
def answer_space_search(lo, hi, is_feasible):
    result = hi  # or lo, depending on direction
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if is_feasible(mid):
            result = mid
            hi = mid - 1   # try to minimise further
        else:
            lo = mid + 1
    return result

例：荷物の発送容量

LeetCode 1011 'Capacity to Ship Packages Within D Days'：重みのリストと D 日が与えられたとき、すべての荷物を順番どおりに D 日以内で発送するために必要な最小の発送容量を求めます。答えは [max(weights), sum(weights)] の範囲にあります。貪欲法でシミュレーションし、すべての荷物を D 日以内に発送できれば、その容量は実現可能です。容量の範囲に対して二分探索を行うと、計算量は O(n log(sum)) になります。

def shipWithinDays(weights, days):
    def can_ship(capacity):
        needed_days, current_load = 1, 0
        for w in weights:
            if current_load + w > capacity:
                needed_days += 1
                current_load = 0
            current_load += w
        return needed_days <= days

    lo, hi = max(weights), sum(weights)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if can_ship(mid):
            hi = mid        # feasible, try smaller
        else:
            lo = mid + 1    # not feasible, need more capacity
    return lo

print(shipWithinDays([1,2,3,4,5,6,7,8,9,10], 5))  # 15
print(shipWithinDays([3,2,2,4,1,4], 3))            # 6

例：Koko のバナナ食べ

LeetCode 875 'Koko Eating Bananas'：Koko は 1 時間あたり K 本のバナナを食べられ、H 個の山をちょうど H 時間で食べ終えることを目指して、K を最小化します。探索範囲は [1, max(piles)] です。チェックでは、速度が K のときの合計時間を sum(ceil(pile/K)) で求め、それが <= H でなければなりません。これを満たす最小の K を二分探索で求めます。

import math

def minEatingSpeed(piles, h):
    def can_finish(k):
        return sum(math.ceil(p / k) for p in piles) <= h

    lo, hi = 1, max(piles)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if can_finish(mid):
            hi = mid      # feasible, try lower speed
        else:
            lo = mid + 1  # too slow
    return lo

print(minEatingSpeed([3,6,7,11], 8))    # 4
print(minEatingSpeed([30,11,23,4,20], 5))  # 30

例：花束を作るための最小日数

LeetCode 1482 'Minimum Number of Days to Make m Bouquets'：それぞれ k 本の、隣り合って咲いた花からなる花束を m 個作る必要があります。花 i は bloomDay[i] 日目に咲きます。日数を対象に二分探索します。範囲は [1, max(bloomDay)] です。実現可能性のチェックでは、連続して咲いた花の数を数え、m 個の花束を作れるかどうかを確認します。単調性により、日 d で可能なら、日 d+1 でも可能です。

def minDays(bloomDay, m, k):
    if m * k > len(bloomDay):
        return -1  # impossible

    def can_make(day):
        bouquets = consecutive = 0
        for bd in bloomDay:
            if bd <= day:
                consecutive += 1
                if consecutive == k:
                    bouquets += 1
                    consecutive = 0
            else:
                consecutive = 0
        return bouquets >= m

    lo, hi = 1, max(bloomDay)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if can_make(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

print(minDays([1,10,3,10,2], 3, 1))  # 3
print(minDays([1,10,3,10,2], 3, 2))  # -1

探索範囲を特定する

適切な [lo, hi] の範囲を選ぶことが重要です。lo は答えとして可能な最小値（例：最小要素、1、0）にし、hi は答えとして可能な最大値（例：すべての要素の合計、最大要素、n）にします。hi が小さすぎると有効な答えを見落としますが、大きすぎても問題ありません。二分探索は O(log(hi - lo)) 回のステップで収束するためです。

# Choosing lo and hi for common problems:
# Capacity to ship: lo=max(weights), hi=sum(weights)
# Koko eating:      lo=1,            hi=max(piles)
# Square root:      lo=1,            hi=x
# Allocate books:   lo=max(pages),   hi=sum(pages)

def isqrt_bs(x):
    if x < 2:
        return x
    lo, hi = 1, x
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if mid * mid <= x:
            lo = mid + 1
        else:
            hi = mid
    return lo - 1

for n in [0, 1, 4, 8, 9, 15, 16]:
    print(f'isqrt({n}) = {isqrt_bs(n)}')

最大化と最小化：方向が重要

答えの範囲に対する二分探索には 2 つの種類があります。答えを最小化する場合は、チェックに合格したらより小さい値を試す（hi = mid）一方、失敗したらより大きい値を試します（lo = mid + 1）。答えを最大化する場合は、チェックに合格したらより大きい値を試し（lo = mid + 1、mid を候補として保存）、失敗したらより小さい値を試します（hi = mid - 1）。コードを書く前に、どちらの方向を探索するのかを必ず明確にしてください。

# Maximise: largest x such that f(x) is feasible
def max_feasible(lo, hi, is_feasible):
    result = lo - 1   # sentinel: no feasible answer found
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if is_feasible(mid):
            result = mid
            lo = mid + 1  # try larger
        else:
            hi = mid - 1
    return result

# Example: largest k such that k^2 <= 50
print(max_feasible(1, 50, lambda k: k * k <= 50))  # 7

最小ページ数の割り当て（典型問題）

n 冊の本と pages[]、k 人の学生が与えられたとき、本を連続する区間ごとに割り当て、最も多くのページを読む学生のページ数をできるだけ少なくします。答え（可能な最大値の最小値）に対して二分探索を行います。実現可能性のチェックでは、本を貪欲に学生へ割り当てます。本を追加すると現在の最大値を超える場合は、新しい学生に割り当てます。必要な学生数が <= k なら、その最大値は実現可能です。

def allocate_min_pages(pages, k):
    if k > len(pages):
        return -1

    def is_feasible(max_pages):
        students, current = 1, 0
        for p in pages:
            if p > max_pages:
                return False  # single book exceeds limit
            if current + p > max_pages:
                students += 1
                current = 0
            current += p
        return students <= k

    lo, hi = max(pages), sum(pages)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if is_feasible(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

print(allocate_min_pages([12, 34, 67, 90], 2))  # 113
print(allocate_min_pages([10, 20, 30, 40], 2))  # 60

答えの範囲に対する探索の計算量分析

時間計算量は O(n × log(range)) です。ここで n は実現可能性チェックのコスト（通常は線形走査）、range = hi - lo は答えの範囲の大きさを表します。たとえば、ページ数の合計が 10⁹ で、実現可能性チェックが O(n) の場合、全体の計算量は O(n log 10⁹) ≈ O(30n) となり、O(n²) の全探索よりはるかに優れています。

空間計算量は、二分探索自体では O(1) であり、これに実現可能性チェックで使用する領域が加わります。

import math

# Compare brute force vs answer-space binary search
# For sum = 10^9 and n = 10^5:
brute_ops = 10**9         # try every possible answer
bsearch_ops = 10**5 * math.log2(10**9)  # n * log(range)
print(f'Brute force: {brute_ops:,.0f} operations')
print(f'Binary search: {bsearch_ops:,.0f} operations')
print(f'Speedup: {brute_ops / bsearch_ops:,.0f}x')

ソート済み行列の K 番目に小さい要素

LeetCode 378 'Kth Smallest Element in a Sorted Matrix'：n×n 行列の各行と各列がソートされています。答えの値を [matrix[0][0], matrix[n-1][n-1]] の範囲で二分探索します。実現可能性のチェックでは、左下隅から始めるポインターを使って mid 以下の要素数を数え、O(n) で実行します。mid 以下の要素が少なくとも k 個存在する最小の値を求めます。

def kthSmallest(matrix, k):
    n = len(matrix)

    def count_le(mid):
        count, row, col = 0, n - 1, 0
        while row >= 0 and col < n:
            if matrix[row][col] <= mid:
                count += row + 1
                col += 1
            else:
                row -= 1
        return count

    lo, hi = matrix[0][0], matrix[n-1][n-1]
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if count_le(mid) >= k:
            hi = mid
        else:
            lo = mid + 1
    return lo

matrix = [[1,5,9],[10,11,13],[12,13,15]]
print(kthSmallest(matrix, 8))  # 13

答えの範囲に対する問題を見分ける

答えの範囲に対する二分探索に適した問題には、いくつかの共通する特徴があります。問題が最小値または最大値を求めており、答えが有界な数値範囲にあり、候補となる答えを増やす（または減らす）と実現可能性が単調に良くなる、または悪くなることです。代表的なキーワードには 'minimum possible maximum'、'at most k operations'、'within d days' などがあります。

これらの特徴に気づいたら、すぐに lo と hi を定義し、実現可能性関数を作って、テンプレートを適用してください。この構造化された方法は、面接でほとんど失敗しません。

理解度チェック

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

レッスンのまとめ

このレッスンでは、数値範囲上で実現可能性関数が単調である場合に、答えの範囲に対する二分探索を適用できること、テンプレートでは [lo, hi] を探索し、can_achieve チェックによって探索範囲を半分にすること、そして全体の計算量が、1 回の実現可能性チェックのコストを n とすると O(n log(range)) になることを学びました。次は連結リストと Node クラスに進みます。

よくある質問