Binary Search Interview Problems — Off-by-One Traps

Binary search shows up in roughly 15-20% of technical screening rounds at top tech companies — not because it's exotic, but because it's a clean signal for how a candidate thinks about elimination, boundaries, and edge cases under pressure. Miss the pattern and you'll write an O(n) linear scan where an O(log n) search was expected. Spot it and you look like the engineer who actually understands algorithmic trade-offs.

The real problem isn't the algorithm itself — most people can recite 'split in half, compare, repeat'. The problem is recognizing WHEN to apply it, and then getting the boundary conditions exactly right without an off-by-one bug that only surfaces on arrays of length 1 or 2. Interviewers know this, which is why they love edge cases like single-element arrays, all-duplicate arrays, and rotated sorted arrays.

By the end of this article you'll be able to identify the four core binary search patterns by sight, implement each one without looking up the boundary conditions, and explain your reasoning out loud — which is exactly what interviewers want to hear. We'll go from the textbook template all the way through rotation, condition-based search, and answer-space binary search with full runnable code for each.

The Template That Eliminates Off-By-One Bugs Forever

Every binary search variant is a specialization of one template. Until you've internalized this template so deeply that you can write it in your sleep, you'll keep making subtle off-by-one errors that cause infinite loops or miss the target by one index.

The key design decision in any binary search is: what does your loop invariant guarantee? The invariant we'll use is this — the answer, if it exists, is always inside the closed interval [left, right]. That single rule dictates every boundary choice that follows.

When left == right there's exactly one candidate left. That's why the loop condition is left <= right, not left < right. And when you calculate mid, you use left + (right - left) / 2 instead of (left + right) / 2 — both give the same index, but the second one silently overflows when left and right are large integers, a bug that killed a famous Java binary search implementation in the JDK for nearly a decade.

The moment you find target at mid, you return immediately. If target < array[mid], the right half is useless, so right = mid - 1. If target > array[mid], the left half is useless, so left = mid + 1. This is the foundation every other pattern builds on.

package io.thecodeforge.search;

public class ClassicBinarySearch {

    /**
     * Standard iterative Binary Search.
     * LeetCode 704: Binary Search
     * 
     * @param nums   Sorted array of integers
     * @param target Integer to find
     * @return Index of target, or -1 if not found
     */
    public int search(int[] nums, int target) {
        if (nums == null || nums.length == 0) return -1;

        int left = 0;
        int right = nums.length - 1;

        while (left <= right) {
            // Use unsigned right shift or (left + (right - left) / 2) to prevent overflow
            int mid = left + (right - left) / 2;

            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return -1;
    }
}

Finding Boundaries: First and Last Position of a Duplicated Target

Once you've nailed the classic template, the first upgrade interviewers throw at you is: 'What if the array has duplicates? Find the first occurrence, or the last occurrence.' This is LeetCode 34, and it's a direct test of whether you understand binary search deeply or just memorized the basic version.

The trick is to NOT return the moment you find the target. Instead, you record the current mid as a candidate answer, then deliberately push the search boundary to keep looking. For the first occurrence you push right = mid - 1 (keep searching left). For the last occurrence you push left = mid + 1 (keep searching right).

This turns a single-target search into a boundary search. The loop still terminates — left and right still converge — but now instead of exiting early you let the loop exhaust all possibilities, always keeping the best answer you've seen so far.

This pattern has a name: Left Boundary Binary Search and Right Boundary Binary Search. Recognizing them as named patterns rather than one-off tricks is what lets you adapt quickly when interviewers change the constraint mid-question.

package io.thecodeforge.search;

public class BoundarySearch {

    /**
     * LeetCode 34: Find First and Last Position of Element in Sorted Array
     */
    public int[] searchRange(int[] nums, int target) {
        int[] result = {-1, -1};
        result[0] = findBoundary(nums, target, true);
        result[1] = findBoundary(nums, target, false);
        return result;
    }

    private int findBoundary(int[] nums, int target, boolean isFirst) {
        int left = 0, right = nums.length - 1;
        int ans = -1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                ans = mid;
                if (isFirst) {
                    right = mid - 1; // Shrink towards the left
                } else {
                    left = mid + 1;  // Shrink towards the right
                }
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return ans;
    }
}

Searching a Rotated Sorted Array — The Classic Hard-Mode Variant

Here's where interviewers separate people who 'know binary search' from people who truly understand it. A rotated sorted array is an array like [40, 55, 63, 7, 18, 29] — it was originally sorted but has been rotated around a pivot. Half the array is still sorted. That's the key insight.

At every mid-point you can determine in O(1) which half is sorted — just compare array[left] with array[mid]. If array[left] <= array[mid], the left half is cleanly sorted. Otherwise, the right half is. Once you know which half is sorted, you can check in O(1) whether the target falls inside that sorted half. If yes, search there. If no, search the other half.

You never need to find the pivot explicitly. The binary search logic handles everything in one pass. That's the elegant part — and it's also what trips people up who try to pre-compute the pivot index before searching. Two passes where one will do is a sign of incomplete understanding, and interviewers notice.

package io.thecodeforge.search;

public class RotatedSearch {

    /**
     * LeetCode 33: Search in Rotated Sorted Array
     */
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) return mid;

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

Answer-Space Binary Search — When the Input Isn't Even an Array

This is the pattern that separates intermediate from advanced binary search practitioners — and it trips up even experienced engineers. Answer-space binary search applies when you can't binary search the input directly, but you CAN binary search the space of possible answers.

The template is: define a minimum and maximum possible answer (your left and right pointers). Write a feasibility function that checks 'is this candidate answer good enough?'. Then binary search over the answer space, always recording the best valid answer found so far. This is the most powerful and least-recognized form of binary search in interview settings.

package io.thecodeforge.search;

public class KokoEatingBananas {

    /**
     * LeetCode 875: Koko Eating Bananas
     * Binary search on the 'speed' (answer space).
     */
    public int minEatingSpeed(int[] piles, int h) {
        int left = 1, right = 1_000_000_000;
        int ans = right;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (canFinish(piles, h, mid)) {
                ans = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }

    private boolean canFinish(int[] piles, int h, int k) {
        long totalHours = 0;
        for (int p : piles) {
            totalHours += (p + k - 1) / k; // Ceiling division
        }
        return totalHours <= h;
    }
}

Finding Square Root Using Binary Search — Integer Square Root with Precision

A classic answer-space binary search example: find the integer square root of a non-negative integer x. You don't need Math.sqrt or Newton's method — binary search over [0, x] works beautifully and is often what interviewers expect for LeetCode 69 (Sqrt(x)).

The feasibility function is simple: check if mid * mid <= x. If yes, move left to mid + 1 (the square root could be larger). If no, move right to mid - 1. Record the candidate answer (mid) each time the check passes, because the last valid mid before the loop ends is the integer square root.

This problem is a perfect warm-up before tackling more complex answer-space problems like Koko Eating Bananas or Split Array Largest Sum. It's also a good test of overflow handling — mid * mid can overflow int if x is large. Use long for the multiplication.

package io.thecodeforge.search;

public class SqrtBinarySearch {

    /**
     * LeetCode 69: Sqrt(x)
     * Returns the integer floor of square root.
     */
    public int mySqrt(int x) {
        if (x == 0) return 0;
        int left = 1, right = x, ans = 0;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            // Use long to avoid overflow when mid * mid
            if ((long) mid * mid <= (long) x) {
                ans = mid;   // mid is a candidate
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return ans;
    }
}

Searching a 2D Sorted Matrix with Binary Search

Interviewers often combine matrix traversal with binary search. LeetCode 240 (Search a 2D Matrix II) presents a matrix where rows and columns are sorted independently. The trick is to start from the top-right corner: you can eliminate an entire row or column in each step.

But there's also a binary search pattern here: if you treat each row as a sorted array, you could binary search each row individually — O(m log n). Or you could use the 'staircase' approach which is O(m+n). The interview trick is to recognise when the matrix is 'row and column sorted' vs 'fully sorted row-major' (LeetCode 74). For fully sorted row-major, you can flatten the matrix logically (using modulo arithmetic) and do one binary search in O(log(m*n)).

Know which variant you face: if the first element of each row is > last element of previous row, it's row-major sorted and you can do a true 2D binary search. If only rows and columns are sorted individually, use the top-right elimination method.

package io.thecodeforge.search;

public class MatrixSearch {

    /**
     * LeetCode 240: Search a 2D Matrix II (row and column sorted)
     * Top-right corner elimination O(m+n)
     */
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0) return false;
        int row = 0, col = matrix[0].length - 1;

        while (row < matrix.length && col >= 0) {
            if (matrix[row][col] == target) {
                return true;
            } else if (matrix[row][col] < target) {
                row++; // all elements in this row to the left are smaller, so go down
            } else {
                col--; // all elements below in this column are larger, so go left
            }
        }
        return false;
    }

    /**
     * LeetCode 74: Search a 2D Matrix (fully sorted row-major)
     * Single binary search over flattened array
     */
    public boolean searchMatrixRowMajor(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0) return false;
        int m = matrix.length, n = matrix[0].length;
        int left = 0, right = m * n - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            int midVal = matrix[mid / n][mid % n];
            if (midVal == target) return true;
            else if (midVal < target) left = mid + 1;
            else right = mid - 1;
        }
        return false;
    }
}