Binary Search Variations: Complete Reference

TL;DR

• Bottom line: Binary search applies far beyond sorted arrays — use it on any monotonic predicate (a function that transitions from false to true or vice versa) to find the boundary in O(log n) time.
• Key tool: lo/hi pointers with strict invariant maintenance — always ensure the search space shrinks by at least 1 each iteration.
• Watch out for: Off-by-one errors in boundary updates and integer overflow in mid calculation — use lo + (hi - lo) / 2 instead of (lo + hi) / 2.
• Works with: Any language, any sorted/monotonic search space. Patterns are language-agnostic.

Constraints

• The search space MUST be monotonic: either the array is sorted, or a boolean predicate transitions from all-false to all-true (or vice versa). Binary search on non-monotonic data produces incorrect results silently.
• Always use overflow-safe mid calculation: mid = lo + (hi - lo) / 2. The expression (lo + hi) / 2 caused a bug in Java's Arrays.binarySearch that went undetected for 20 years.
• When using while (lo < hi) with lo = mid (not mid + 1), you MUST use ceiling division mid = lo + (hi - lo + 1) / 2 to prevent infinite loops.
• For rotated array problems, always determine which half is sorted before deciding where the target lies. Comparing arr[lo] vs arr[mid] tells you which half is sorted.

Quick Reference

Decision Tree

START
├── Is the search space a sorted array?
│   ├── YES → Need exact match?
│   │   ├── YES → Standard binary search (while lo <= hi)
│   │   └── NO → Need first element >= target?
│   │       ├── YES → Lower bound pattern
│   │       └── NO → Need first element > target?
│   │           ├── YES → Upper bound pattern
│   │           └── NO → Need count of target?
│   │               └── YES → lower_bound + upper_bound combo
│   └── NO ↓
├── Is it a rotated sorted array?
│   ├── YES → Need minimum element?
│   │   ├── YES → Rotated array minimum (compare mid vs hi)
│   │   └── NO → Rotated array search (check sorted half)
│   └── NO ↓
├── Is there a monotonic predicate (false→true or true→false)?
│   ├── YES → Is the predicate on the answer itself?
│   │   ├── YES → Search on answer space
│   │   └── NO → First true / last true pattern
│   └── NO ↓
├── Is the array bitonic (increases then decreases)?
│   ├── YES → Peak element pattern
│   └── NO ↓
├── Is it a sorted 2D matrix?
│   ├── YES → Matrix binary search (flatten to 1D)
│   └── NO ↓
└── DEFAULT → Binary search NOT applicable — use hash map, linear scan, or BFS/DFS

Step-by-Step Guide

1. Implement standard binary search

The foundation of all variations. Use while lo <= hi for exact match. [src1]

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

Verify: binary_search([1, 3, 5, 7, 9], 5) → expected: 2

2. Implement lower bound (first >= target)

Used for insertion points, counting, and range queries. Never return early — narrow to convergence. [src2]

def lower_bound(arr, target):
    lo, hi = 0, len(arr)       # hi = len(arr), NOT len(arr)-1
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return lo

Verify: lower_bound([1, 3, 5, 5, 7], 5) → expected: 2

3. Implement upper bound (first > target)

Combined with lower bound: range [lower_bound, upper_bound) contains all copies of target. [src2]

def upper_bound(arr, target):
    lo, hi = 0, len(arr)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] <= target:  # <= instead of <
            lo = mid + 1
        else:
            hi = mid
    return lo

Verify: upper_bound([1, 3, 5, 5, 7], 5) → expected: 4

4. Implement search in rotated sorted array

Determine which half is sorted by comparing arr[lo] vs arr[mid], then check if target lies in the sorted half. [src6]

def search_rotated(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] == target:
            return mid
        if arr[lo] <= arr[mid]:           # left half sorted
            if arr[lo] <= target < arr[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:                               # right half sorted
            if arr[mid] < target <= arr[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1

Verify: search_rotated([4, 5, 6, 7, 0, 1, 2], 0) → expected: 4

5. Implement search on answer space

When you can verify if a candidate works but cannot directly compute the answer, binary search the answer itself. [src4]

def search_on_answer(lo, hi, is_feasible):
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if is_feasible(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

Verify: search_on_answer(1, 100, lambda x: x * x >= 50) → expected: 8

6. Implement peak element finder

For bitonic arrays, compare arr[mid] with arr[mid+1] to decide direction. [src5]

def find_peak(arr):
    lo, hi = 0, len(arr) - 1
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] < arr[mid + 1]:
            lo = mid + 1
        else:
            hi = mid
    return lo

Verify: find_peak([1, 3, 7, 5, 2]) → expected: 2

Code Examples

Python: Complete binary search toolkit

# Input:  sorted array and target value
# Output: index or insertion point depending on function

from bisect import bisect_left, bisect_right

# Python's standard library provides lower/upper bound:
# bisect_left  = lower_bound (first index >= target)
# bisect_right = upper_bound (first index > target)

arr = [1, 3, 5, 5, 5, 7, 9]
target = 5

first_occurrence = bisect_left(arr, target)      # 2
last_occurrence = bisect_right(arr, target) - 1   # 4
count = bisect_right(arr, target) - bisect_left(arr, target)  # 3

JavaScript: Lower bound and search on answer

// Input:  sorted array, target value
// Output: index of first element >= target

function lowerBound(arr, target) {
  let lo = 0, hi = arr.length;
  while (lo < hi) {
    const mid = lo + ((hi - lo) >> 1);
    if (arr[mid] < target) lo = mid + 1;
    else hi = mid;
  }
  return lo;
}

// Search on answer: find minimum capacity to ship within D days
function shipWithinDays(weights, days) {
  let lo = Math.max(...weights);
  let hi = weights.reduce((a, b) => a + b, 0);
  while (lo < hi) {
    const mid = lo + ((hi - lo) >> 1);
    if (canShip(weights, days, mid)) hi = mid;
    else lo = mid + 1;
  }
  return lo;
}

Java: Overflow-safe binary search

// Input:  sorted int array, target
// Output: index of target, or -1

public static int binarySearch(int[] arr, int target) {
    int lo = 0, hi = arr.length - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;  // overflow-safe
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

// Rotated array: find minimum element
public static int findMin(int[] arr) {
    int lo = 0, hi = arr.length - 1;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] > arr[hi]) lo = mid + 1;
        else hi = mid;
    }
    return arr[lo];
}

C++: Using STL and custom predicates

// Input:  sorted vector, target value
// Output: iterator to first element >= target

#include <algorithm>
#include <vector>

std::vector<int> v = {1, 3, 5, 5, 7, 9};
auto lb = std::lower_bound(v.begin(), v.end(), 5);  // first 5
auto ub = std::upper_bound(v.begin(), v.end(), 5);  // points to 7
int count = std::distance(lb, ub);                    // 2

// Custom predicate with partition_point (C++20):
auto it = std::partition_point(
    v.begin(), v.end(),
    [&](int x) { return (long long)x * x < n; }
);

Anti-Patterns

Wrong: Integer overflow in mid calculation

// BAD — overflows when lo + hi > Integer.MAX_VALUE
int mid = (lo + hi) / 2;

Correct: Overflow-safe mid calculation

// GOOD — subtraction cannot overflow when both are non-negative
int mid = lo + (hi - lo) / 2;
// Or in C++20: std::midpoint(lo, hi)

Wrong: Infinite loop with lo = mid

# BAD — when hi - lo == 1, mid == lo, lo never advances
while lo < hi:
    mid = lo + (hi - lo) // 2  # floor division
    if condition(mid):
        hi = mid
    else:
        lo = mid               # INFINITE LOOP

Correct: Always shrink the search space

# GOOD — use mid + 1 for lo assignment
while lo < hi:
    mid = lo + (hi - lo) // 2
    if condition(mid):
        hi = mid
    else:
        lo = mid + 1           # guarantees progress

Wrong: Off-by-one in search boundaries

# BAD — hi should be len(arr) for lower_bound, not len(arr)-1
def lower_bound(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return lo  # wrong when target > all elements

Correct: Use half-open interval [lo, hi)

# GOOD — hi = len(arr) handles "target greater than all" correctly
def lower_bound(arr, target):
    lo, hi = 0, len(arr)       # half-open [0, n)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return lo  # returns len(arr) if target > all

Wrong: Rotated array — comparing with wrong boundary

# BAD — comparing mid with lo for minimum finding
def find_min_rotated(arr):
    lo, hi = 0, len(arr) - 1
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] > arr[lo]:   # wrong comparison
            lo = mid + 1
        else:
            hi = mid
    return arr[lo]  # fails on [2, 1]

Correct: Compare mid with hi for minimum finding

# GOOD — comparing with hi correctly identifies minimum half
def find_min_rotated(arr):
    lo, hi = 0, len(arr) - 1
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] > arr[hi]:   # min in right half
            lo = mid + 1
        else:
            hi = mid
    return arr[lo]  # correctly returns 1 for [2, 1]

Common Pitfalls

• Integer overflow in mid calculation: In Java/C++, (lo + hi) exceeds Integer.MAX_VALUE for large arrays. Fix: mid = lo + (hi - lo) / 2. This affected production code for decades. [src3]
• Wrong loop condition (< vs <=): Using while lo < hi when you need while lo <= hi either misses the last candidate or causes infinite loops. Fix: Use <= for exact match (return inside loop), < for convergence (return after loop). [src2]
• Forgetting to handle empty results: Lower bound returns len(arr) when target exceeds all elements — not checking causes index-out-of-bounds. Fix: Always check if lo < len(arr) and arr[lo] == target. [src5]
• Infinite loop from lo = mid: When hi = lo + 1, floor division gives mid = lo, and lo = mid makes no progress. Fix: Use lo = mid + 1 or ceiling division. [src1]
• Non-monotonic data: Binary search on unsorted data or non-monotonic functions silently returns wrong answers. Fix: Verify monotonicity before applying. [src7]
• Duplicates in rotated array: Worst case degrades to O(n) when arr[lo] == arr[mid] == arr[hi]. Fix: Skip duplicates with lo++ or hi--. [src6]

When to Use / When Not to Use

Important Caveats

• Binary search has two distinct families: exact match (while lo <= hi, return inside loop) and boundary finding (while lo < hi, return after loop). Mixing conventions is the #1 source of bugs.
• In languages without arbitrary-precision integers (C, C++, Java, Go), always use the overflow-safe mid formula. Python and JavaScript (BigInt) do not have this issue for standard integers.
• The "search on answer space" pattern requires proving the feasibility predicate is monotonic. If feasibility is not monotonic, binary search silently returns wrong answers.
• For floating-point binary search, use a fixed number of iterations (e.g., 100) instead of epsilon comparison to avoid precision issues.
• Duplicates in rotated arrays degrade worst-case complexity from O(log n) to O(n). Verify whether the problem guarantees distinct elements.