Binary Search Patterns: Five Variants Every Senior Engineer Knows

Scenario context

Binary search has five patterns beyond the classic "find the target": leftmost position, rightmost position, rotated array search, minimum in rotated array, and 2D matrix search. The root of every off-by-one bug is a mismatched loop condition and boundary update. Learn the invariant for each pattern and you will never write a broken binary search again.

You think binary search is trivial — until your interview…

This walkthrough focuses on Why "Find First Position" Trips Up Even Senior Engineers.

Before making a design choice, clarify:

• You think binary search is trivial — until your interviewer asks for the first position of a target in a sorted array with duplicates, and your standard implementation returns a middle occurrence instead of the leftmost…
• Or they ask you to search a rotated sorted array, and your algorithm returns -1 on valid inputs.
• Binary search looks simple: split the search space in half.

Concepts in play: sorting-and-searching-algorithms, jvm-internals-and-garbage-collection, database-indexing

Stage 1 — The Six Binary Search Patterns in Java

• Pattern 1: Classic Exact Search — the baseline every other pattern extends Pattern 2: Leftmost Position — first occurrence of target When you find the target, you do not return immediately.
• Instead, you record mid as a candidate and continue searching left ( right = mid - 1 ).
• The loop uses left <= right and converges to the leftmost occurrence.
• Pattern 3: Rightmost Position — last occurrence of target Mirror of Pattern 2: when you find the target, record it and continue right ( left = mid + 1 ).

public class BinarySearchPatterns {

    // Pattern 1: Find exact target, return index or -1
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;  // No overflow
            if (nums[mid] == target) return mid;
            else if (nums[mid] < target) left = mid + 1;
            else right = mid - 1;
        }
        return -1;
    }

    // Pattern 2: First (leftmost) occurrence of target; returns -1 if absent
    public int searchFirst(int[] nums, int target) {
        int left = 0, right = nums.length - 1, result = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                result = mid;     // Candidate found — keep searching left
                right = mid - 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return result;
    }

Observable outcome: Pattern 3: Rightmost Position — last occurrence of target Mirror of Pattern 2: when you find the target, record it and continue right ( left = mid + 1 ).

Stage 2 — Deep Dive: Binary Search Invariants and Integer Overflow

• Binary Search Internals: The Loop Invariant Every correct binary search maintains a loop invariant : a property that is true before every iteration and after the loop terminates.
• The invariant tells you where the answer must be.
• For the classic exact search: - Invariant: If target exists in nums , it is in the range [left, right] .
• • Termination: When left right , the range is empty and the target is not present.

Observable outcome: - Termination: When left right , the range is empty and the target is not present.

Stage 3 — Binary Search in the Real World: Sorted Indexes and Range Queries

• Database B-tree index lookups: Every relational database (PostgreSQL, MySQL, Oracle) stores index entries in a sorted B-tree.
• Finding a specific key in a B-tree is structurally identical to binary search on a sorted array, with each "halving" step being a tree node traversal instead of an array mid-point.
• The query WHERE user id = 12345 on an indexed column executes O(log n) comparisons.
• Range queries with leftmost / rightmost patterns: Finding all orders placed between January 1 and January 31 requires two binary searches: one for the leftmost record with date = Jan 1 and one for the rightmost record w…

Observable outcome: Range queries with leftmost / rightmost patterns: Finding all orders placed between January 1 and January 31 requires two binary searches: one for the leftmost record with date = Jan 1 and one for the rightmost record w…

Stage 4 — Where Binary Search Fails and How to Avoid Off-by-One Errors

• Binary search only works on sorted, random-access data.
• Linked lists cannot support binary search efficiently because mid requires O(n) traversal.
• Unsorted arrays produce meaningless results.
• Always verify the sorted precondition before applying binary search.

Observable outcome: Always verify the sorted precondition before applying binary search.

Stage 5 — Which Binary Search Pattern to Use When

• Quick pick rule: If the problem says "find first" or "find last" in a sorted array — use Patterns 2 or 3 with the result candidate variable.
• If it says "rotated" — use Pattern 4 with the sorted-half check.
• If it says "minimum" in a rotated array — use Pattern 5 with while left < right .

Observable outcome: If it says "minimum" in a rotated array — use Pattern 5 with while left < right .

Stage 6 — Pattern Walkthroughs with Full Worked Examples

• Example 1: Leftmost Position on [1, 2, 2, 2, 3] , target = 2 Step-by-step trace of Pattern 2 (already shown in Deep Dive).
• A classic binary search would return index 2 — the wrong answer.
• Example 2: Minimum in [4, 5, 6, 7, 0, 1, 2] Trace of Pattern 5: Example 3: Search [[1,3,5],[7,9,11],[13,15,17]] for target = 9 Matrix is 3×3, n = 3.
• Flattened, it is [1,3,5,7,9,11,13,15,17] .

Observable outcome: Flattened, it is [1,3,5,7,9,11,13,15,17] .

End-to-end outcome

After working through the stages, you should be able to explain:

• Using (left + right) / 2 instead of left + (right - left) / 2 .
• This overflows for arrays with more than ~2 billion elements.
• • Six patterns cover every binary search interview problem: classic, leftmost, rightmost, rotated search, minimum in rotated, and 2D matrix.
• Each has a specific loop condition and boundary update.

Alternatives considered

The Three-Way Branch at Every Binary Search Comparison

At each iteration, exactly one of three outcomes occurs.

Failure and degraded modes

The source does not isolate a separate failure mode. Limits that matter for the scenario are called out in the stage decisions above.