Binary Search on the Answer
Guess the result and check feasibility.
Binary Search on the Answer is a free Coding 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 Coding Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
Guess, Then Verify
Sometimes you cannot compute the answer directly, but you can check a guess. Binary search on the answer turns hard optimization into easy checking.
# guess X, ask: is X feasible?The Magic Property
It works when feasibility is monotonic: if a value works, every larger (or smaller) value also works. That ordering is what you search.
# feasible(X) true => feasible(X+1) trueBound the Answer Range
Identify the smallest and largest possible answers as low and high. For min capacity, low is one item and high is the total sum.
low, high = max(weights), sum(weights)Write the Feasibility Check
The heart of the method is a can(X) function that returns true if the guess X is achievable. It usually runs in linear time.
def can(cap):
# simulate and return True/False
...Example: Ship in D Days
Given daily capacity cap, greedily fill days and count them. can(cap) is true when the day count stays within the limit D.
def can(cap):
days, load = 1, 0
for w in weights:
if load + w > cap:
days += 1; load = 0
load += w
return days <= DSearch the Minimum Capacity
You want the smallest cap that passes. This is a first-true search over capacities, so reuse the high = mid template.
while low < high:
mid = (low + high) // 2Keep the Feasible Half
If can(mid) is true, a smaller capacity might still work, so set high = mid. Otherwise raise the floor with low = mid + 1.
if can(mid):
high = mid
else:
low = mid + 1Mind the Time Budget
Total cost is O(check x log range). A linear check over a billion-wide range is only about 30 checks, fast enough for tight limits.
# log2(1e9) is about 30 iterationsMaximize Instead of Minimize
To find the largest feasible value, flip the logic: search the last true. Move low up when feasible and shave high when not.
if can(mid):
low = mid
else:
high = mid - 1Real-Valued Answers
For floating answers, loop a fixed count like 100 times instead of integer mid. Each round halves the interval, reaching tiny precision fast.
for _ in range(100):
mid = (low + high) / 2Spotting the Pattern
Phrases like minimum largest, maximum smallest, or smallest k that works are signals to binary-search the answer. Train your eye for them.
# 'minimize the maximum' => search answerQuick Check
Decide when binary search on the answer applies.
Recap: Search the Answer
You can now bound the answer, write a feasibility check, and binary-search for the minimum or maximum. Hard problems become guess-and-verify. 🏆
Frequently asked questions
Is the “Binary Search on the Answer” lesson free?
Yes — the full text of “Binary Search on the Answer” is free to read here on the web, and the Coding 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 Coding Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “Binary Search on the Answer”?
Guess the result and check feasibility. You practise Coding 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 Coding Interview Prep?
No prior experience is required. Coding 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 “Binary Search on the Answer” 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 Coding Interview Prep lesson?
Yes. Every Coding 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.
All lessons in this course
- Classic Binary Search Without Bugs
- bisect_left and bisect_right
- First True: Predicate Binary Search
- Binary Search on the Answer