Answer-Space Binary Search
Treat a continuous answer range as a search space to solve problems like minimum-time-to-complete-jobs and capacity-to-ship-packages.
Answer-Space Binary Search is a free DSA Interview Prep lesson on CoddyKit — lesson 4 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the DSA Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
Binary Search on Answer Space
Most people know binary search for finding a value in a sorted array. But binary search is even more powerful when applied to the space of possible answers. Instead of searching an array, you search a numeric range — for example, 'what is the minimum number of days to ship all packages?' — and use a check function to decide whether a candidate answer is feasible.
This technique converts many optimisation problems from O(n²) or worse to O(n log(max_answer)).
The Answer-Space Template
The template has three components. First, define the search range [lo, hi] that brackets all valid answers. Second, write a feasibility check can_achieve(mid) that returns True if the mid value is achievable. Third, binary search over [lo, hi]: if can_achieve(mid), move toward a smaller (or larger) answer; otherwise move in the other direction.
The key property: the feasibility function must be monotone — once an answer is feasible, all values beyond it are also feasible (or all below are infeasible).
# 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 resultExample: Capacity to Ship Packages
LeetCode 1011 'Capacity to Ship Packages Within D Days': given a list of weights and D days, find the minimum ship capacity to ship all packages in order within D days. The answer lies in [max(weights), sum(weights)]. A capacity is feasible if a greedy simulation fits all packages within D days. Binary search over the capacity range gives O(n log(sum)) time.
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)) # 6Example: Koko Eating Bananas
LeetCode 875 'Koko Eating Bananas': Koko can eat K bananas per hour; she wants to finish H piles in exactly H hours, minimising K. The search range is [1, max(piles)]. The check: at rate K, total hours = sum(ceil(pile/K)), which must be <= H. We binary search for the smallest K that satisfies this.
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)) # 30Example: Minimum Days to Make Bouquets
LeetCode 1482 'Minimum Number of Days to Make m Bouquets': you need m bouquets, each of k consecutive bloomed flowers. Flower i blooms on day bloomDay[i]. Binary search on the day: the range is [1, max(bloomDay)]. The feasibility check counts consecutive bloomed flowers and sees if m bouquets can be formed. Monotone property: if day d works, day d+1 also works.
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)) # -1Identifying the Search Range
Choosing the right [lo, hi] range is critical. lo should be the minimum possible answer (e.g., the minimum element, 1, or 0) and hi should be the maximum possible answer (e.g., sum of all elements, max element, or n). Setting hi too small misses valid answers; setting it too large is fine because binary search will still converge in O(log(hi - lo)) steps.
# 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 vs Minimise: Direction Matters
Answer-space binary search has two flavours. Minimise the answer: when the check passes, try smaller (hi = mid); when it fails, try larger (lo = mid + 1). Maximise the answer: when the check passes, try larger (lo = mid + 1, saving mid as candidate); when it fails, try smaller (hi = mid - 1). Always clarify which direction you are searching before coding.
# 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)) # 7Allocate Minimum Pages (Classic Problem)
Given n books with pages[] and k students, allocate books contiguously so the student with the most pages reads as few as possible. Binary search on the answer (minimum possible maximum). The feasibility check greedily assigns books to students: when adding a book would exceed the current maximum, give it to a new student. If students needed <= k, the maximum is achievable.
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)) # 60Complexity Analysis of Answer-Space Search
The time complexity is O(n × log(range)) where n is the cost of the feasibility check (usually a linear scan) and range = hi - lo (the size of the answer space). For example, if pages sum to 10⁹ and the feasibility check is O(n), the total time is O(n log 10⁹) ≈ O(30n), which is far better than O(n²) brute force.
Space complexity is O(1) for the binary search itself, plus whatever the feasibility check uses.
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')Kth Smallest in Sorted Matrix
LeetCode 378 'Kth Smallest Element in a Sorted Matrix': each row and column of an n×n matrix is sorted. Binary search on the answer value in [matrix[0][0], matrix[n-1][n-1]]. The feasibility check counts elements <= mid using a pointer starting from the bottom-left corner, running in O(n). Find the smallest value where at least k elements are <= mid.
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)) # 13Recognising Answer-Space Problems
Problems suited for answer-space binary search share common signals: the question asks for a minimum or maximum value, the answer lies in a bounded numeric range, and increasing (or decreasing) the candidate answer makes feasibility monotonically better or worse. Classic keywords include 'minimum possible maximum', 'at most k operations', and 'within d days'.
When you spot these signals, immediately define lo and hi, write the feasibility function, and apply the template. This structured approach rarely fails in interviews.
Quick Check
Test your understanding of Data Structures & Algorithms — Coding Interview Prep concepts from this lesson.
Lesson Recap
In this lesson you learned: answer-space binary search applies when a feasibility function is monotone over a numeric range, the template searches [lo, hi] and uses a can_achieve check to halve the search space, and total complexity is O(n log(range)) where n is the cost of one feasibility check. Next up we shift to linked lists and the Node class.
Frequently asked questions
Is the “Answer-Space Binary Search” lesson free?
Yes — the full text of “Answer-Space Binary Search” is free to read here on the web, and the DSA Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the DSA Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “Answer-Space Binary Search”?
Treat a continuous answer range as a search space to solve problems like minimum-time-to-complete-jobs and capacity-to-ship-packages. You practise DSA Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start DSA Interview Prep?
No prior experience is required. DSA Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 4 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Answer-Space Binary Search” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this DSA Interview Prep lesson?
Yes. Every DSA Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.