Binary Search on Answer Technique in DSA Go

Mental Model

We guess an answer and check if it works, then adjust the guess up or down until we find the best answer.

Analogy: Imagine trying to find the right temperature to bake a cake by guessing and adjusting based on whether it's undercooked or burnt.

low
 ↑
[? ? ? ? ? ? ? ? ? ?]
                      ↑
high

We pick a middle guess between low and high and test it.

Dry Run Walkthrough

Input: array: [1, 2, 3, 4, 5], target sum: 8, find max length of subarray with sum <= 8

Goal: Find the longest subarray length whose sum is at most 8 using binary search on answer

Step 1: Set low=1, high=5 (array length), mid=(1+5)/2=3; check if subarray length 3 can have sum <= 8

array: [1, 2, 3, 4, 5]
Trying length=3
Subarrays: [1,2,3]=6 ≤ 8 (valid)
[2,3,4]=9 > 8 (invalid)
[3,4,5]=12 > 8 (invalid)

Why: We test mid length to see if any subarray of this length meets the sum condition

Step 2: Since length 3 is valid (some subarray sum ≤ 8), set low=mid+1=4 to try longer subarrays

low=4, high=5
Trying length=4

Why: Try to find a longer valid subarray

Step 3: Check subarrays of length 4: [1,2,3,4]=10 > 8 (invalid), [2,3,4,5]=14 > 8 (invalid)

No valid subarray of length 4

Why: Length 4 is too long, sum exceeds target

Step 4: Since length 4 invalid, set high=mid-1=3

low=4, high=3 (low > high, stop)

Why: No longer subarray possible, binary search ends

Result:

Longest valid subarray length = 3

Annotated Code

DSA Go

package main

import "fmt"

func canFindSubarray(arr []int, length int, target int) bool {
    sum := 0
    for i := 0; i < length; i++ {
        sum += arr[i] // sum first 'length' elements
    }
    if sum <= target {
        return true
    }
    for i := length; i < len(arr); i++ {
        sum += arr[i] - arr[i-length] // slide window
        if sum <= target {
            return true
        }
    }
    return false
}

func binarySearchOnAnswer(arr []int, target int) int {
    low, high := 1, len(arr)
    result := 0
    for low <= high {
        mid := (low + high) / 2
        if canFindSubarray(arr, mid, target) {
            result = mid // mid length works, try longer
            low = mid + 1
        } else {
            high = mid - 1 // mid length too long, try shorter
        }
    }
    return result
}

func main() {
    arr := []int{1, 2, 3, 4, 5}
    target := 8
    fmt.Printf("Longest valid subarray length = %d\n", binarySearchOnAnswer(arr, target))
}

for low <= high {

binary search loop to narrow down answer range

mid := (low + high) / 2

guess middle length to test

if canFindSubarray(arr, mid, target) {

check if subarray of length mid meets sum condition

result = mid // mid length works, try longer

record valid length and try longer

low = mid + 1

increase lower bound to search longer lengths

high = mid - 1 // mid length too long, try shorter

decrease upper bound to search shorter lengths

sum += arr[i] - arr[i-length] // slide window

update sum for next subarray by sliding window

Output

Longest valid subarray length = 3

Complexity Analysis

Time: O(n log n) because each binary search step does a sliding window check over n elements

Space: O(1) because only a few variables and counters are used

vs Alternative: Naive approach checks all subarrays O(n^2), binary search on answer reduces to O(n log n)

Edge Cases

empty array

returns 0 because no subarray exists

DSA Go

low, high := 1, len(arr) // high=0 means loop never runs

target smaller than smallest element

returns 0 because no subarray sum can be ≤ target

DSA Go

if canFindSubarray(arr, mid, target) { ... } else { ... }

all elements equal and sum exactly target

returns max length fitting sum exactly

DSA Go

sum <= target check in canFindSubarray

When to Use This Pattern

When you need to find the best numeric answer but can't check all answers directly, use binary search on answer to guess and verify efficiently.

Common Mistakes

Mistake: Not updating low and high correctly after checking mid
Fix: Set low = mid + 1 when mid is valid, else high = mid - 1

Mistake: Checking subarray sums inefficiently inside binary search
Fix: Use sliding window to check sums in O(n) per guess

Summary

It finds the best answer by guessing and checking with binary search.

Use it when the answer is a number and you can verify guesses efficiently.

The key is to turn the problem into yes/no questions about guesses and narrow down.