Binary Search

Binary Search

Binary search is the single most important searching algorithm for coding interviews. It transforms an O(n) scan into an O(log n) lookup — searching a billion-element array in about 30 steps. But its power extends far beyond sorted arrays. Any problem with a monotonic predicate — a condition that flips from false to true at some threshold — can be solved with binary search. Master this algorithm and you unlock an entire category of interview problems.

Prerequisites

Binary search requires one structural guarantee: the data (or predicate) must be monotonic. For a sorted array, this means elements are in non-decreasing order. For optimization problems, this means there exists a boundary value where feasibility changes from impossible to possible (or vice versa). Without monotonicity, binary search gives incorrect results. Always verify this property before reaching for the algorithm.

Basic Binary Search — Iterative

The iterative version is what you should write in interviews. It uses constant space, avoids stack overflow, and is easy to reason about:

public static int binarySearch(int[] array, int target) {
    int lo = 0;
    int hi = array.length - 1;

    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;

        if (array[mid] == target) {
            return mid;
        } else if (array[mid] < target) {
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }
    return -1;
}

Three details demand attention:

1. Midpoint calculation: mid = lo + (hi - lo) / 2, not (lo + hi) / 2. When lo and hi are both large (close to Integer.MAX_VALUE), their sum overflows a 32-bit integer, producing a negative number and an ArrayIndexOutOfBoundsException. The subtraction form avoids this entirely. This bug famously existed in Java’s Arrays.binarySearch implementation for nearly a decade before being discovered. Always use the safe form.

2. Loop condition: lo <= hi means the search space [lo, hi] is non-empty. When lo > hi, the space is empty and the target is absent.

3. Pointer updates: lo = mid + 1 and hi = mid - 1 exclude the already-checked element mid from the next iteration. Failing to add/subtract 1 creates infinite loops — one of the most common binary search bugs.

Recursive Binary Search

The recursive version exists for completeness. Use it only if an interviewer specifically asks for recursion:

public static int binarySearchRecursive(int[] array, int target, int lo, int hi) {
    if (lo > hi) {
        return -1;
    }

    int mid = lo + (hi - lo) / 2;

    if (array[mid] == target) {
        return mid;
    } else if (array[mid] < target) {
        return binarySearchRecursive(array, target, mid + 1, hi);
    } else {
        return binarySearchRecursive(array, target, lo, mid - 1);
    }
}

The recursive version uses O(log n) stack space — acceptable for most inputs but problematic for very large arrays (millions of elements). Java does not guarantee tail-call optimization, so deep recursion can throw StackOverflowError. Prefer iterative in production and in interviews unless told otherwise.

Off-By-One Errors — The #1 Binary Search Bug

More binary search implementations fail from off-by-one errors than from any other cause. The cure is to adopt an invariant-based approach: define precisely what lo and hi represent, and maintain that definition rigorously.

Three Invariant Styles

Style	lo represents	hi represents	Loop condition	Pointer updates
[lo, hi] (closed)	First valid candidate	Last valid candidate	lo <= hi	lo = mid + 1, hi = mid - 1
[lo, hi) (half-open)	First valid candidate	One past last valid	lo < hi	lo = mid + 1, hi = mid
(lo, hi] (half-open)	One before first valid	Last valid candidate	lo < hi	lo = mid, hi = mid - 1

Pick one style and use it for every binary search problem in the interview. Switching styles mid-problem invites mistakes. The [lo, hi] closed-interval style is the most intuitive and the one used in the basic template above.

Here is the mental model for [lo, hi]:

• Invariant: The answer, if it exists, is somewhere in [lo, hi].
• Termination: When lo > hi, the interval is empty, so the answer does not exist.
• Progress: Every iteration either increases lo or decreases hi, guaranteeing termination.

If you can state your invariant clearly, you can derive the correct pointer updates mechanically. No guessing. No trial-and-error.

Lower Bound — First Occurrence of Target

Standard binary search finds some occurrence of the target. But what if the array contains duplicates and you need the leftmost one? This is lower_bound (also called bisectLeft):

public static int bisectLeft(int[] array, int target) {
    int lo = 0;
    int hi = array.length;

    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;

        if (array[mid] < target) {
            lo = mid + 1;
        } else {
            hi = mid;
        }
    }
    return lo;
}

Notice the differences from exact-match binary search:

• hi starts at array.length, not array.length - 1. This uses a half-open interval [lo, hi).
• No early return on equality. When array[mid] == target, we set hi = mid to keep searching left for an earlier occurrence.
• The return value is the insertion point: the index of the first element ≥ target. If the target exists, lo points to its first occurrence. If not, lo points to where it would be inserted.

Counting Occurrences

With bisectLeft and bisectRight, counting occurrences of a target in a sorted array is a one-liner:

int count = bisectRight(array, target) - bisectLeft(array, target);

Both operations are O(log n), so the total is O(log n) — far better than scanning the array linearly.

Upper Bound — First Element Greater Than Target

bisectRight finds the insertion point after all existing copies of the target:

public static int bisectRight(int[] array, int target) {
    int lo = 0;
    int hi = array.length;

    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;

        if (array[mid] <= target) {
            lo = mid + 1;
        } else {
            hi = mid;
        }
    }
    return lo;
}

The only change from bisectLeft: the comparison uses <= instead of <. When array[mid] == target, we go right (lo = mid + 1) instead of left, converging to the first position after all copies.

Binary Search on Answer

This is the most powerful and underappreciated binary search pattern. Instead of searching within an array, you search the answer space itself.

The Pattern

Many optimization problems ask: “What is the minimum (or maximum) value of X such that some constraint is satisfied?” If the feasibility function is monotonic — meaning once X is large enough to be feasible, all larger values are also feasible — you can binary search on X.

Template:

public static int binarySearchOnAnswer(int lo, int hi) {
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;

        if (isFeasible(mid)) {
            hi = mid;       // mid works — try smaller
        } else {
            lo = mid + 1;   // mid doesn't work — need larger
        }
    }
    return lo;
}

The key insight: you never search an array. You define a range of possible answers [lo, hi], and you use a feasible(mid) function to determine whether mid is a valid answer. The binary search converges on the smallest feasible answer.

Example: Koko Eating Bananas

Problem: Koko has n piles of bananas with piles[i] bananas in each pile. She can eat at speed k bananas per hour (one pile per hour, finishing early means waiting). She has h hours. Find the minimum k such that she can eat all bananas within h hours.

Monotonic property: If Koko can finish at speed k, she can finish at any speed > k. The feasibility flips from false to true at some threshold speed — binary search on that speed.

public static int minEatingSpeed(int[] piles, int h) {
    int lo = 1;
    int hi = 0;
    for (int pile : piles) {
        hi = Math.max(hi, pile);
    }

    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;

        if (canFinish(piles, mid, h)) {
            hi = mid;
        } else {
            lo = mid + 1;
        }
    }
    return lo;
}

private static boolean canFinish(int[] piles, int speed, int hours) {
    long totalHours = 0;
    for (int pile : piles) {
        totalHours += (pile + speed - 1) / speed; // ceiling division
    }
    return totalHours <= hours;
}

Analysis: The answer space is [1, max(piles)]. Binary search makes O(log(max)) iterations. Each iteration calls canFinish, which scans all piles in O(n). Total: O(n log(max)).

Example: Split Array Largest Sum

Problem: Split an array into m contiguous subarrays to minimize the largest subarray sum.

Monotonic property: If you can split the array such that no subarray sum exceeds limit, you can do it for any larger limit. Binary search on the limit.

The feasible function greedily assigns elements to subarrays: keep adding elements to the current subarray until the sum would exceed limit, then start a new subarray. If you need more than m subarrays, the limit is too small.

public static int splitArray(int[] nums, int m) {
    int lo = 0;
    int hi = 0;
    for (int num : nums) {
        lo = Math.max(lo, num);  // minimum possible: largest single element
        hi += num;                // maximum possible: entire array in one subarray
    }

    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;

        if (canSplit(nums, m, mid)) {
            hi = mid;
        } else {
            lo = mid + 1;
        }
    }
    return lo;
}

private static boolean canSplit(int[] nums, int maxSubarrays, int maxSum) {
    int subarrays = 1;
    long currentSum = 0;
    for (int num : nums) {
        if (currentSum + num > maxSum) {
            subarrays++;
            currentSum = num;
            if (subarrays > maxSubarrays) {
                return false;
            }
        } else {
            currentSum += num;
        }
    }
    return true;
}

This pattern recurs across dozens of problems: minimum capacity to ship packages within D days, maximum distance between gas stations, allocating pages to students. Once you recognize the monotonic feasibility structure, the code writes itself.

Classic Problems

Search in Rotated Sorted Array

A sorted array has been rotated at an unknown pivot. For example, [4, 5, 6, 7, 0, 1, 2] is [0, 1, 2, 4, 5, 6, 7] rotated at index 4. Find the index of a target value in O(log n).

Key insight: When you compute mid, at least one of the two halves [lo, mid] or [mid, hi] is sorted. Check which half is sorted, then check if the target falls within that sorted half. If it does, search there. If not, search the other half.

public static int searchRotated(int[] nums, int target) {
    int lo = 0;
    int hi = nums.length - 1;

    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;

        if (nums[mid] == target) {
            return mid;
        }

        if (nums[lo] <= nums[mid]) {
            // left half [lo, mid] is sorted
            if (nums[lo] <= target && target < nums[mid]) {
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        } else {
            // right half [mid, hi] is sorted
            if (nums[mid] < target && target <= nums[hi]) {
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
    }
    return -1;
}

Walk through [4, 5, 6, 7, 0, 1, 2] searching for 0:

1. lo=0, hi=6, mid=3 → nums[3]=7. Left half [4,5,6,7] is sorted. Target 0 is not in [4,7]. Go right: lo=4.
2. lo=4, hi=6, mid=5 → nums[5]=1. Left half [0,1] — check: nums[4]=0 <= nums[5]=1, sorted. Target 0 is in [0,1). Go left: hi=4.
3. lo=4, hi=4, mid=4 → nums[4]=0. Found.

Find Minimum in Rotated Sorted Array

Find the minimum element in a rotated sorted array (no duplicates):

public static int findMin(int[] nums) {
    int lo = 0;
    int hi = nums.length - 1;

    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;

        if (nums[mid] > nums[hi]) {
            lo = mid + 1;   // minimum is in the right half
        } else {
            hi = mid;        // mid could be the minimum
        }
    }
    return nums[lo];
}

The invariant: the minimum is always within [lo, hi]. If nums[mid] > nums[hi], the rotation point (and the minimum) is in (mid, hi]. Otherwise, the minimum is in [lo, mid].

Search a 2D Matrix

Given an m × n matrix where each row is sorted and the first element of each row is greater than the last element of the previous row, search for a target.

Treat the 2D matrix as a flattened 1D sorted array. Map index i to row i / cols and column i % cols:

public static boolean searchMatrix(int[][] matrix, int target) {
    int rows = matrix.length;
    int cols = matrix[0].length;
    int lo = 0;
    int hi = rows * cols - 1;

    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        int value = matrix[mid / cols][mid % cols];

        if (value == target) {
            return true;
        } else if (value < target) {
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }
    return false;
}

Time: O(log(m × n)) = O(log m + log n). Space: O(1). The matrix’s structure gives you sorted data for free — no flattening needed, only index arithmetic.

Peak Element

Find any peak element (an element strictly greater than its neighbors) in an unsorted array. The array has the property that nums[-1] = nums[n] = -∞.

public static int findPeakElement(int[] nums) {
    int lo = 0;
    int hi = nums.length - 1;

    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;

        if (nums[mid] < nums[mid + 1]) {
            lo = mid + 1;  // peak is to the right
        } else {
            hi = mid;       // mid could be the peak
        }
    }
    return lo;
}

Why does this work on unsorted data? Because the virtual boundaries nums[-1] = -∞ and nums[n] = -∞ guarantee at least one peak exists. If nums[mid] < nums[mid + 1], the values are rising to the right, and a peak must exist in [mid + 1, hi] (values cannot rise forever — they must come down before reaching the boundary nums[n] = -∞). Symmetric reasoning applies when values are rising to the left.

First Bad Version

You have n versions [1, 2, ..., n]. Some version introduced a bug, and all subsequent versions are bad. Given an API boolean isBadVersion(int version), find the first bad version.

This is pure binary search on a boolean predicate:

public static int firstBadVersion(int n) {
    int lo = 1;
    int hi = n;

    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;

        if (isBadVersion(mid)) {
            hi = mid;       // mid is bad — first bad is at mid or earlier
        } else {
            lo = mid + 1;   // mid is good — first bad is later
        }
    }
    return lo;
}

This is the bisectLeft template applied to an abstract predicate instead of an array. The pattern is identical: find the first position where the predicate becomes true.

Complexity

Variant	Time	Space
Iterative binary search	O(log n)	O(1)
Recursive binary search	O(log n)	O(log n) — call stack
Binary search on answer	O(n log R)	O(1) — R is the answer range
Rotated array search	O(log n)	O(1)
2D matrix search	O(log(m × n))	O(1)

The O(log n) factor comes from halving the search space with each iteration. After k iterations, the remaining space is n / 2^k. Setting n / 2^k = 1 and solving gives k = log₂(n).

Common Mistakes

Integer overflow in midpoint. (lo + hi) / 2 overflows when lo + hi > Integer.MAX_VALUE. Always use lo + (hi - lo) / 2.

Wrong loop condition. Using lo < hi when the invariant requires lo <= hi (or vice versa) causes missed elements or infinite loops. Derive the condition from your invariant — do not guess.

Forgetting to exclude mid. Writing lo = mid instead of lo = mid + 1 when mid has already been checked creates an infinite loop when lo == mid (which happens when hi - lo == 1).

Not verifying monotonicity. Applying binary search to a non-monotonic function produces wrong answers silently. Before coding, confirm that the predicate is monotonic.

Off-by-one in answer range. For binary search on answer, setting lo too high or hi too low excludes the correct answer. Think about edge cases: what are the absolute minimum and maximum possible answers?

Interviewer Tips

Binary search is the most commonly tested searching algorithm across all major tech companies. Here is what interviewers look for:

1. Correct midpoint calculation. Using lo + (hi - lo) / 2 signals that you understand integer overflow. This is a basic expectation.
2. Clear invariants. State what lo and hi represent before writing the loop. Interviewers reward candidates who reason about correctness rather than hacking until the code passes.
3. Recognizing “search on answer” problems. Many candidates miss these because the problem does not mention “search” or “sorted array.” Train yourself to spot the monotonic feasibility pattern.
4. Handling edge cases. Empty arrays, single-element arrays, all-duplicates, target smaller than all elements, target larger than all elements. Test these mentally before declaring your solution complete.
5. Knowing when binary search does NOT apply. If the data has no monotonic property, say so. Forcing binary search where it does not belong is worse than using linear search.

Binary search looks deceptively simple — three pointers and a while loop. The difficulty lies in getting every detail right under pressure. Practice until the invariant-based approach becomes automatic. When you can write a correct binary search in two minutes without debugging, you own one of the most powerful tools in the interview toolkit.