TLDR: 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.

---

📖 Why "Find First Position" Trips Up Even Senior Engineers

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 one. 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. But the devil is entirely in the boundary conditions. The wrong combination of < vs <=, mid vs mid - 1, and left = mid vs left = mid + 1 produces bugs that pass most tests and fail exactly the edge cases an interviewer checks.

There are five distinct binary search patterns:

Each pattern has a different loop condition and boundary update rule. Understanding the loop invariant for each — what must be true about left and right before every iteration — eliminates off-by-one errors permanently.

---

🔍 The Off-By-One Problem: Loop Condition Determines the Search Space

Every binary search maintains a search window [left, right]. The loop condition specifies what "non-empty window" means:

• while (left <= right): the window is [left, right] — inclusive on both ends. The loop runs while at least one element is in the window. Used for exact search with early return.
• while (left < right): the window is [left, right) — the loop converges to left == right. No early return needed because left == right is the answer. Used for boundary-finding patterns (leftmost, rightmost, minimum).

The mid calculation must never use (left + right) / 2 — this overflows when left + right > Integer.MAX_VALUE. Always use mid = left + (right - left) / 2.

Mixing these two conditions with the wrong boundary updates is the source of 90% of binary search bugs.

---

⚙️ The Six Binary Search Patterns in Java

Pattern 1: Classic Exact Search — the baseline every other pattern extends

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: 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 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;
    }

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).

    // Pattern 3: Last (rightmost) occurrence of target; returns -1 if absent
    public int searchLast(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 right
                left = mid + 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return result;
    }

Pattern 4: Search in Rotated Sorted Array — find pivot, then binary search (LeetCode 33)

One half of the array is always sorted. Check which half contains mid, then determine if the target falls in the sorted half.

    // Pattern 4: Search in rotated sorted array (distinct values)
    public int searchRotated(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 [left..mid] is sorted
            if (nums[left] <= nums[mid]) {
                if (nums[left] <= target && target < nums[mid]) right = mid - 1;
                else left = mid + 1;
            } else {
                // Right half [mid..right] is sorted
                if (nums[mid] < target && target <= nums[right]) left = mid + 1;
                else right = mid - 1;
            }
        }
        return -1;
    }

Pattern 5: Minimum in Rotated Sorted Array — binary search on the pivot (LeetCode 153)

The minimum is at the rotation pivot. Compare nums[mid] with nums[right]: if nums[mid] > nums[right], the pivot is to the right of mid; otherwise it is to the left.

    // Pattern 5: Find minimum element in rotated sorted array
    public int findMin(int[] nums) {
        int left = 0, right = nums.length - 1;
        while (left < right) {                    // Converge to the minimum
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[right]) left = mid + 1;  // Min is right of mid
            else right = mid;                             // Min is at mid or left of mid
        }
        return nums[left];  // left == right at convergence
    }

Pattern 6: Search in 2D Matrix — treat as flattened 1D array (LeetCode 74)

An m × n matrix sorted row by row can be treated as a sorted 1D array of length m × n. Map mid to (mid / n, mid % n) to access the cell.

    // Pattern 6: Search in row-sorted m x n matrix
    public boolean searchMatrix(int[][] matrix, int target) {
        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 val = matrix[mid / n][mid % n];  // Map 1D index to 2D cell
            if (val == target) return true;
            else if (val < target) left = mid + 1;
            else right = mid - 1;
        }
        return false;
    }
}

---

🧠 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.

For the leftmost position search:

• Invariant: All elements to the left of left are < target; the answer (if it exists) is in [left, right].
• Termination: left > right; the last recorded result holds the leftmost position.

For the minimum in rotated array (while left < right):

• Invariant: The minimum element is always in [left, right].
• Termination: left == right; nums[left] is the minimum.

Here is a trace of Pattern 2 (leftmost) on nums = [1, 2, 2, 2, 3], target = 2:

Performance Analysis: O(log n) Time and O(1) Space

Time Complexity: O(log n)

Each iteration halves the search window: window size goes from n → n/2 → n/4 → … → 1. After k iterations, the window has n / 2^k elements. The loop terminates when n / 2^k ≤ 1, so k = log₂(n). For a 1-billion-element array, binary search needs at most 30 comparisons.

Space Complexity: O(1)

Binary search uses three integer variables (left, right, mid) regardless of input size. No auxiliary data structure is needed. This is a significant advantage over hash table lookup (O(n) space) for read-heavy sorted datasets.

Why mid = left + (right - left) / 2 matters: If left = 1,500,000,000 and right = 1,700,000,000, then left + right = 3,200,000,000 which overflows a signed 32-bit integer (Integer.MAX_VALUE = 2,147,483,647). The subtraction form left + (right - left) / 2 never overflows because right - left is always ≤ Integer.MAX_VALUE.

---

📊 The Three-Way Branch at Every Binary Search Comparison

At each iteration, exactly one of three outcomes occurs. The flow is the same for all six patterns; only the boundary update differs:

flowchart TD
    A["Compute mid = left + (right - left) / 2"]
    B{"nums[mid] vs target"}
    C["Target found at mid\n(or record candidate)"]
    D["Search right half\nleft = mid + 1"]
    E["Search left half\nright = mid - 1\n(or right = mid for convergence patterns)"]
    F{"left <= right\n(or left < right)?"}
    G["Return result"]

    F -->|Yes| A
    A --> B
    B -->|"nums[mid] == target"| C
    B -->|"nums[mid] < target"| D
    B -->|"nums[mid] > target"| E
    C --> F
    D --> F
    E --> F
    F -->|No| G

    style C fill:#4CAF50,color:#fff
    style D fill:#2196F3,color:#fff
    style E fill:#FF9800,color:#fff
    style G fill:#9C27B0,color:#fff

The only difference between the six patterns is what happens in the "Target found" branch (return immediately vs record and continue) and whether right = mid - 1 or right = mid (for convergence-style loops).

---

🌍 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 with date <= Jan 31. This is exactly Patterns 2 and 3 applied to a sorted date column. Most database engines implement this as two B-tree traversals.

Java's Collections.sort + Collections.binarySearch: The Collections.binarySearch method is Pattern 1 (exact search). It returns a non-negative index on success, or -(insertion point) - 1 on failure — where the insertion point is where the target would be inserted to maintain sorted order. This negative encoding lets callers distinguish "not found" from "found at index 0" without a second return value.

---

⚖️ 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.

The three most common off-by-one bugs:

1. mid = (left + right) / 2 with large indices: Integer overflow. Always use left + (right - left) / 2.

2. right = mid vs right = mid - 1 in leftmost/rightmost patterns: For convergence-style loops (while left < right), use right = mid to avoid skipping the answer. For exact-search loops (while left <= right), use right = mid - 1 to shrink the window.

3. Using while left < right with an early return on match: If you return mid in the middle of a while left < right loop, the left == right termination condition never applies — the function returns early. This is fine for exact search but will cause infinite loops if the boundary update ever produces left == mid without shrinking the window.

Common failure mode in Pattern 5 (minimum in rotated array): Using right = mid - 1 instead of right = mid. When nums[mid] <= nums[right], the minimum could be exactly at mid. Setting right = mid - 1 excludes this candidate, causing the function to return the wrong element on the final iteration.

---

🧭 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.

---

🧪 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). Result: index 1. 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]. Binary search finds mid = 4, matrix[4/3][4%3] = matrix[1][1] = 9. Found at index 4 in the flattened array.

---

🛠️ Java's Arrays.binarySearch: What Negative Return Values Mean

Java's standard library includes Arrays.binarySearch(int[] a, int key) — a Pattern 1 (exact search) implementation:

import java.util.Arrays;

int[] sorted = {1, 3, 5, 7, 9, 11};

int idx = Arrays.binarySearch(sorted, 7);   // Returns 3 (index of 7)
int missing = Arrays.binarySearch(sorted, 6); // Returns -4 (-(insertion point) - 1)
// Insertion point for 6 is index 3 (between 5 and 7)
// Encoded as -(3) - 1 = -4

// Recover insertion point from negative result:
int insertionPoint = -missing - 1;  // = 3

The negative encoding -(insertion point) - 1 is chosen so that both -0 and 0 can be distinguished: a return of 0 means "found at index 0"; a return of -1 means "not found, insertion point is 0." This is Java's way of returning two pieces of information (found/not-found and position) through a single int return value.

Critical caveat: Arrays.binarySearch is undefined for unsorted arrays and returns an arbitrary index for duplicate values — it does not guarantee leftmost or rightmost position. For those cases, use the Pattern 2 and Pattern 3 implementations above.

---

📚 Lessons Learned: The Five Binary Search Mistakes Everyone Makes

1. Using (left + right) / 2 instead of left + (right - left) / 2. This overflows for arrays with more than ~2 billion elements. Use the subtraction form in all binary search implementations — it costs nothing and prevents a subtle correctness bug on large inputs.

2. Using while (left <= right) for boundary-finding patterns. Boundary-finding patterns (leftmost, minimum in rotated) need the loop to converge to left == right. A <= loop with right = mid can run forever when left == right - 1 and nums[mid] <= nums[right], because mid = left and right = mid = left leaves right unchanged.

3. Forgetting to record the candidate in leftmost/rightmost patterns. These patterns never return inside the loop. They update a result variable when a match is found, then continue narrowing. Forgetting the result variable means the answer is lost when the loop ends.

4. Applying binary search to unsorted or partially sorted data. Binary search assumes the monotone property: either the left half or the right half of the array always contains the answer based on a comparison with mid. Violating this assumption produces incorrect results with no error signal.

5. Confusing Arrays.binarySearch return value sign conventions. Java returns the index if found (≥ 0) and -(insertion point) - 1 if not found (< 0). The insertion point is one more than the index of the last element smaller than the key — not the index of the element itself.

---

📌 Summary: Binary Search Mastery in Five Points

• 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.
• The mid overflow fix is always left + (right - left) / 2 — never (left + right) / 2.
• while (left <= right) is for exact search with early return; while (left < right) is for convergence to a boundary. Mixing them is the source of most off-by-one bugs.
• In leftmost and rightmost patterns, do not return on match. Record the candidate and continue narrowing the search window.
• Arrays.binarySearch is Pattern 1 only. It does not guarantee leftmost or rightmost position on duplicate values — implement Patterns 2 and 3 manually.

Binary search is not about halving an array. It is about maintaining a shrinking invariant window that always contains the answer. Understand the invariant for each pattern and off-by-one errors disappear.

---

📝 Practice Quiz

1. An array [1, 2, 2, 2, 3] is searched for target 2 using the classic binary search (Pattern 1). The standard implementation returns index 2. Which pattern should you use to guarantee index 1 (the first occurrence) is returned?

   • A) Pattern 1 with a linear scan backward from the found index
   • B) Pattern 2 (leftmost): when found, record the index and set right = mid - 1 to continue left
   • C) Pattern 3 (rightmost): when found, record the index and set left = mid + 1 Correct Answer: B

2. You are searching a rotated sorted array [4, 5, 6, 7, 0, 1, 2] for target 0. At the first iteration, left=0, right=6, mid=3, nums[mid]=7. Which half of the array is sorted, and where do you search next?

   • A) Right half [mid..right] is sorted because 7 > 2; target 0 is in range [0..2]; search right: left = mid + 1
   • B) Left half [left..mid] is sorted because 4 ≤ 7; target 0 is not in [4..7]; search right: left = mid + 1
   • C) Left half is sorted; target 0 is in [4..7]; search left: right = mid - 1 Correct Answer: B

3. In Pattern 5 (minimum in rotated array), why does the boundary update use right = mid instead of right = mid - 1 when nums[mid] <= nums[right]?

   • A) To avoid skipping the minimum, which could be located exactly at mid
   • B) To prevent the loop from running too many iterations
   • C) Because mid - 1 would cause an ArrayIndexOutOfBoundsException Correct Answer: A

4. (Open-ended challenge) Java's Arrays.binarySearch returns a negative value when the target is not found. The encoding is -(insertion point) - 1. Explain why the designers chose this encoding rather than simply returning -1 for all not-found cases. What practical use case does this encoding enable, and how would you use it to implement an efficient "insert into sorted array and maintain order" operation?

---

🔗 Related Posts

• Tries (Prefix Trees)
• Hash Tables Explained
• The Ultimate Data Structures Cheat Sheet