Mastery Points
0
Binary Search on Answer in dsa
Context & Logic
Binary Search on Answer is a powerful technique where instead of searching for an element in an array, we search for the 'answer' in a range of possible values.
Example
// Example: Binary search on range [low, high]
function minMaxSum(arr, k) {
let low = Math.max(...arr), high = arr.reduce((a, b) => a + b, 0);
let ans = high;
while (low <= high) {
let mid = Math.floor((low + high) / 2);
if (isPossible(arr, mid, k)) { ans = mid; high = mid - 1; }
else low = mid + 1;
}
return ans;
}Step-by-Step Logic
1
Define the range for the potential answer [low, high].
2
Pick a middle value 'mid'.
3
Check if 'mid' is a valid solution using a helper function.
Complexity Metrics
Time Efficiency
O(n * log(range))
Memory Footprint
O(1)