Coding Patterns

Binary Search Templates

Learn the two main binary search templates: one that discards mid and one that keeps mid as a candidate.

Binary SearchTemplatesJavaCoding Patterns

The Main Question

After checking mid, do I still want to keep mid as a candidate? That determines the template.

Binary search has many variations, and you will see slightly different versions across problems. But for interviews, these are the two main templates worth memorizing.

If one template feels awkward or creates off-by-one bugs, try the other one. Many binary search mistakes come from mixing the two styles accidentally.

Template 1: Discard Mid

Use this when you check mid and then remove it from the search space.

java

int answer = -1;

while (left <= right) {
    int mid = left + (right - left) / 2;

    if (isValid(mid)) {
        answer = mid;
        right = mid - 1;   // discard mid
    } else {
        left = mid + 1;
    }
}

return answer;

while (left <= right) means there is still a candidate left to check when left == right.
right = mid - 1 means mid is removed from the search space.
If mid was a possible answer, save it separately before discarding it.
This template commonly uses an answer variable.

Template 2: Keep Mid

Use this when mid might still be the first, smallest, best, or final answer.

java

while (left < right) {
    int mid = left + (right - left) / 2;

    if (isValid(mid)) {
        right = mid;       // keep mid
    } else {
        left = mid + 1;
    }
}

return left;

while (left < right) stops when the search space has collapsed to one value.
right = mid keeps mid alive as a candidate.
This is useful when mid may be the first or best valid answer.
When the loop ends, left == right, and that value is the answer.

Side-by-Side Mental Model

Question	Discard Mid	Keep Mid
Loop condition	`left <= right`	`left < right`
When valid	Save answer, then use `right = mid - 1`	Keep candidate with `right = mid`
Do we keep mid?	No	Yes
Return value	Usually `answer`	Usually `left`

Example: Koko Eating Bananas

In Koko Eating Bananas, if a speed works, it might still be the minimum valid speed. So the clean template is usually the keep-mid version.

java

while (left < right) {
    int mid = left + (right - left) / 2;

    if (canFinish(piles, h, mid)) {
        right = mid;       // mid may be the minimum speed
    } else {
        left = mid + 1;
    }
}

return left;

The key thought is: “This speed works, but maybe a smaller speed also works. Keep mid as a candidate and search left.”

Common Interview Mistakes

Mixing Templates

Using while (left < right) but also doing right = mid - 1 can accidentally skip the answer.

Forgetting to Save Answer

If you discard mid but mid was valid, you need to save it before moving past it.

Wrong Loop Condition

If left == right still needs to be checked, use the discard-mid template.

Infinite Loops

If the search space does not shrink every iteration, the loop may never terminate.

Final Takeaway

First ask: after checking mid, should mid stay alive? If yes, use the keep-mid template. If no, discard mid and save the answer separately if needed.