Binary Search: The Complete Interview Guide (with Templates)

The mistake that makes binary search feel tricky is thinking it only applies to sorted arrays — its real power is searching any monotonic answer space in O(log n). If you can phrase a problem as "find the smallest/largest value for which a condition flips from false to true," binary search applies, even when there's no array in sight. Master the boundary discipline below and a whole category of problems opens up.

The classic template

def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2     # avoids integer overflow
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

Two details that prevent most bugs: compute mid as lo + (hi - lo) // 2 (not (lo + hi) // 2, which can overflow in fixed-width languages), and be deliberate about the loop boundary — lo <= hi for "find exact value," lo < hi for "converge to a boundary."

The boundary template (the one that matters most)

For "find the first index where a predicate is true" (the workhorse for variations), use a half-open converging search:

def first_true(lo, hi, pred):     # smallest x in [lo, hi] with pred(x) True
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if pred(mid):
            hi = mid              # answer could be mid -> keep it
        else:
            lo = mid + 1          # mid fails -> discard it
    return lo

Almost every binary-search variation is this template with a custom pred.

Common variations

• First/Last position of a target — two boundary searches (first >= target, first > target).
• Search in Rotated Sorted Array — one half is always sorted; decide which half holds the target.
• Find Minimum in Rotated Sorted Array — boundary search comparing mid to hi.
• Find Peak Element — move toward the higher neighbor; the predicate is "is the slope rising."
• Binary Search on the Answer — the big one: guess an answer, write a feasible(x) check, and binary-search the answer range. Examples: Koko Eating Bananas, Split Array Largest Sum, Capacity to Ship Packages.
• Search a 2D Matrix — treat it as a flattened sorted array, or stair-step from a corner.

Recognition cues

• The input is sorted, or
• The answer is a number in a range and you can write a monotonic feasible(x) (if x works, every larger/smaller x works), or
• A brute force is O(n) over a range and you need O(log n).

Common mistakes

• Overflow in mid (use lo + (hi - lo) // 2).
• Wrong boundary update — when keeping mid as a candidate, set hi = mid, not hi = mid - 1.
• Off-by-one / infinite loop — pair lo <= hi with mid ± 1, and lo < hi with hi = mid.
• Forgetting the answer-space framing — many "hard" problems are just binary search on the answer.

Practice problems

Search Insert Position, Find First and Last Position, Find Minimum in Rotated Sorted Array, Search in Rotated Sorted Array, Find Peak Element, Koko Eating Bananas, Split Array Largest Sum, Search a 2D Matrix.

Get the boundary templates into muscle memory — build a plan with our free study-plan generator, or get live feedback in our DSA course.

More interview patterns: Two Pointers · Sliding Window · Dynamic Programming · Graph Algorithms

Written by Amit Singh — Senior SDE at Amazon, Claude Certified Architect, and founder of AlgoEngineer.