Search on Answer is a way to use binary search when the answer itself is a number.
The important idea is:
We binary-search the possible values of the answer, not the input array.
For example, if a problem asks for the minimum possible maximum sum, we can guess a maximum sum and ask:
“Can I solve the problem if this is the maximum allowed sum?”
If the answer is YES, we try a smaller value.
If the answer is NO, we need a larger value.
The check we use for this question is usually called:
feasible(mid)= “Can the problem be solved ifmidis the answer?”
The pattern to recognize
Look for problems that ask you to:
Minimize the maximum or maximize the minimum, and where you can ask “Can I do it with
mid?”
That combination is a strong sign that Search on Answer may be useful.
Core Example
Let’s use a tiny example to make the idea clear.
Suppose:
nums = [2, 3, 4]
k = 2We want to split the array into 2 contiguous parts while making the largest part sum as small as possible.
The possible answer values are:
4 5 6 7 8 9We can test each value by asking:
“Can I split
[2,3,4]into at most 2 parts if no part is allowed to have a sum greater than this value?”
The results are:
4 5 6 7 8 9
✗ ✓ ✓ ✓ ✓ ✓This is the key pattern:
NO → NO → NO → YES → YES → YES
Once a value works, every larger value also works.
That monotonic YES/NO pattern is what allows us to use binary search.
The goal is to find the first YES.
For this example, the first YES is:
5So the answer is 5.
⚠️ Animation & Content Notice
The animation work is not fully finished — some animations may have slight errors.
If there is a major error in the content or if the animation or content is difficult to understand, please contact us at rayyancodingschool@gmail.com.
Binary Search on the Answer — Split Array Largest Sum
We need to split [2,3,4] into k=2 contiguous parts while making the largest part sum as small as possible. Instead of searching the input array, we binary-search possible answers. A candidate answer is a maximum sum that no part is allowed to exceed.
Start with the actual input [2,3,4]. The largest number is 4, so the answer cannot be smaller than 4. The total sum is 9, so the answer cannot be larger than 9. Therefore the answer must be somewhere between 4 and 9. Now comes the trick: instead of trying every value, binary search these possible answers. For each candidate, ask: 'Can I split [2,3,4] into at most 2 parts if no part is allowed to have a sum greater than this candidate?' If yes, try a smaller candidate. If no, try a larger candidate. For this example, 4 is impossible, while 5 works with [2,3] | [4]. Therefore the answer is 5.
1
lo = max(nums) // smallest possible answer
2
hi = sum(nums) // largest possible answer
3
4
while lo < hi:
5
mid = (lo + hi) / 2
6
7
if canSplit(mid):
8
hi = mid // mid works → try smaller
9
else:
10
lo = mid + 1 // mid fails → need a bigger limit
11
12
return lo
13
14
canSplit(limit):
15
parts = 1
16
run = 0
17
18
for x in nums:
19
if run + x > limit:
20
parts++
21
run = 0
22
run += x
23
24
return parts <= k
public int searchOnAnswer(int[] nums, int k) {
// Smallest possible answer = largest element
int lo = 0;
// Largest possible answer = sum of all elements
int hi = 0;
for (int n : nums) {
lo = Math.max(lo, n);
hi += n;
}
while (lo < hi) {
// Guess the middle possible answer
int mid = lo + (hi - lo) / 2;
// Can we solve the problem using mid
// as the maximum allowed sum?
if (feasible(nums, mid, k)) {
// mid works.
// We want the smallest answer,
// so try smaller values.
hi = mid;
} else {
// mid does not work.
// We need a larger answer.
lo = mid + 1;
}
}
return lo;
}def search_on_answer(nums, k):
# Smallest possible answer = largest element
lo = max(nums)
# Largest possible answer = sum of all elements
hi = sum(nums)
while lo < hi:
# Guess the middle possible answer
mid = lo + (hi - lo) // 2
# Can we solve the problem using mid
# as the maximum allowed sum?
if feasible(nums, mid, k):
# mid works.
# Try smaller values.
hi = mid
else:
# mid does not work.
# Need a larger answer.
lo = mid + 1
return loint searchOnAnswer(vector<int>& nums, int k) {
// Smallest possible answer = largest element
int lo = *max_element(nums.begin(), nums.end());
// Largest possible answer = sum of all elements
int hi = accumulate(nums.begin(), nums.end(), 0);
while (lo < hi) {
// Guess the middle possible answer
int mid = lo + (hi - lo) / 2;
// Can we solve the problem using mid
// as the maximum allowed sum?
if (feasible(nums, mid, k)) {
// mid works.
// Try smaller values.
hi = mid;
} else {
// mid does not work.
// Need a larger answer.
lo = mid + 1;
}
}
return lo;
}function searchOnAnswer(nums, k) {
// Smallest possible answer = largest element
let lo = Math.max(...nums);
// Largest possible answer = sum of all elements
let hi = nums.reduce((sum, n) => sum + n, 0);
while (lo < hi) {
// Guess the middle possible answer
const mid = lo + Math.floor((hi - lo) / 2);
// Can we solve the problem using mid
// as the maximum allowed sum?
if (feasible(nums, mid, k)) {
// mid works.
// Try smaller values.
hi = mid;
} else {
// mid does not work.
// Need a larger answer.
lo = mid + 1;
}
}
return lo;
}The flow: choose answer range → check
feasible(mid)→ use monotonicity to discard half the answers.
Minimize vs Maximize
The single most important distinction — which way does feasible move you?
Minimize an answer
feasible(mid) → hi = mid (works → try smaller)Maximize an answer
feasible(mid) → lo = mid + 1 (works → try larger)Before writing code, ask:
If
midworks, what happens when I increasemid?
Monotonic feasibility looks like false false false true true (minimize) or true true true false false (maximize). No such pattern → no binary search.
Common Mistakes
Binary searching the input instead of the answer.
The search space is capacity / speed / time / max-sum — not array indices.
Wrong answer range.
Derive lo and hi explicitly before starting (max element, total sum, …).
Non-monotonic feasibility.
If making mid bigger can flip feasible→infeasible→feasible, binary search gives wrong answers.
Wrong update direction.
Minimize → hi = mid. Maximize → lo = mid + 1. Mixing them silently returns garbage.
Complexity
| Phase | Time |
|---|---|
| Binary search | O(log range) |
| Each check | O(n) |
| Total | O(n log range) |
Premium Content
Unlock Binary Search on Answer and all premium lessons with a subscription.
From ₹199.99/year — See plans