🧩 Python DSA Patterns — Binary Search on Answers 🎯🐍

Some problems don’t ask you to search in an array — instead, you search for the answer itself.

If a problem has a monotonic condition (“possible → possible → possible → impossible”), you can binary-search the answer range to find the minimum or maximum valid value.

This pattern powers popular problems like:

• Minimum speed
• Minimum capacity
• Allocate books
• Split array
• Koko eating bananas

📝 Minimum Speed to Reach on Time

We search for the minimum integer speed such that total time ≤ allowed hours.

import math

def min_speed(dist, hour):
    left, right = 1, 10**7
    answer = right

    def can_reach(speed):
        time = 0
        for i in range(len(dist)):
            if i == len(dist) - 1:
                time += dist[i] / speed
            else:
                time += math.ceil(dist[i] / speed)
        return time <= hour

    while left <= right:
        mid = (left + right) // 2
        if can_reach(mid):
            answer = mid
            right = mid - 1
        else:
            left = mid + 1

    print("Minimum Speed Required:", answer)

min_speed([1,3,2], 2.7)

📝 Koko Eating Bananas

Classic problem: find the minimum eating speed so Koko finishes all piles in h hours.

def koko_speed(piles, h):
    left, right = 1, max(piles)
    answer = right

    def can_finish(speed):
        hours = 0
        for p in piles:
            hours += math.ceil(p / speed)
        return hours <= h

    while left <= right:
        mid = (left + right) // 2
        if can_finish(mid):
            answer = mid
            right = mid - 1
        else:
            left = mid + 1

    print("Minimum Eating Speed:", answer)

koko_speed([3, 6, 7, 11], 8)

📝 Allocate Books (Minimize Maximum Pages)

Distribute books so that the maximum pages any student gets is minimized.

def allocate_books(pages, students):
    if students > len(pages):
        print("Not enough books")
        return

    left, right = max(pages), sum(pages)
    answer = right

    def can_allocate(limit):
        required = 1
        current_sum = 0
        for p in pages:
            if current_sum + p > limit:
                required += 1
                current_sum = p
                if required > students:
                    return False
            else:
                current_sum += p
        return True

    while left <= right:
        mid = (left + right) // 2
        if can_allocate(mid):
            answer = mid
            right = mid - 1
        else:
            left = mid + 1

    print("Minimum Possible Max Pages:", answer)

allocate_books([12, 34, 67, 90], 2)

🧠 Where It Helps

• 🏃 Minimum speed / minimum time
• 🏋️ Minimized maximum workload
• 📦 Shipping capacity problems
• 🍌 Koko Eating Bananas
• 📚 Allocate books
• 🧩 Split array into K subarrays

If you’re searching for minimum X such that condition is possible, this pattern is your go-to.

✅ Takeaway

• Binary search the range, not the array.
• Write a feasibility function (can_do(mid)).
• Monotonic conditions make it work.
• Extremely powerful in optimization & scheduling problems.

🏋️ Practice Problems

1. Koko Eating Bananas
2. Minimize Maximum Page Allocation
3. Minimum Days to Make Bouquets
4. Split Array – Largest Sum
5. Capacity to Ship Packages in D Days

📂 Full Script

The blog covers the essentials — find the complete notebook with all snippets & extras on GitHub Repo 👉 Python DSA Patterns