البحث الثنائي في فضاء الإجابات

البحث الثنائي في فضاء الإجابات

قالب فضاء الإجابات

# 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

مثال: سعة شحن الطرود

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

مثال: تناول كوكو للموز

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

مثال: الحد الأدنى من الأيام لصنع باقات الزهور

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

تحديد نطاق البحث

# 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)}')

التعظيم مقابل التصغير: الاتجاه مهم

# 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

تخصيص الحد الأدنى من الصفحات (مسألة كلاسيكية)

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

تحليل تعقيد البحث في فضاء الإجابات

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 في مصفوفة مرتبة

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

التعرّف على مسائل فضاء الإجابات

اختبار سريع

مراجعة الدرس