Binary Search Variants: Beyond Simple Lookup

Master variations of binary search including lower bound, upper bound, search in rotated array, and fractional searching for optimization problems.

published: April 7, 2026 reading time: 18 min read author: GeekWorkBench

Binary Search Variants: Beyond Simple Lookup

Binary search is deceptively simple—divide the search space in half, eliminate the half that can’t contain the target, repeat. But the textbook implementation only scratches the surface. Real interview problems twist binary search in creative ways: searching in rotated arrays, finding first or last occurrence, locating peak elements, and using binary search to solve continuous optimization problems where the answer isn’t discrete.

Understanding these variants turns binary search from a single algorithm into a powerful problem-solving framework. The key insight is that binary search doesn’t just find values—it finds the boundary between true and false conditions. This boundary-finding perspective unifies all the variants you’ll encounter.

Introduction

The key insight is that binary search doesn’t just find values; it finds the boundary between true and false conditions. This boundary-finding perspective unifies all the variants: lower bound, upper bound, search in rotated arrays, peak finding, and continuous optimization problems (fractional searching).

This matters because O(log n) search is exponentially faster than O(n) linear search for any non-trivial dataset. In interviews, binary search variants test whether you can think abstractly about search spaces rather than just apply the textbook algorithm. The pattern appears in disguised form—finding matrix peaks, searching sorted rotated arrays, and problems that seem unrelated to searching like the square root calculation or gas station problem.

This guide moves from the basic implementation to advanced variants including lower/upper bound searches, handling duplicates, searching in rotated sorted arrays, and using binary search for continuous optimization. Each variant covers the key insight that makes it work, common pitfalls like off-by-one errors in boundary calculations, and when to use each approach.

When to Use

Binary search variants apply when:

Search space is monotonic — Condition transitions from false to true (or vice versa) exactly once
Searching in rotated sorted array — Array was sorted, then rotated at a pivot point
Finding first/last occurrence — Need leftmost or rightmost position of target
Optimization problems — Continuous search space where you binary search on the answer
Peak finding — Array has exactly one peak where neighbors are smaller

When Not to Use

Unsorted data without a monotonic property
Finding all occurrences rather than boundaries
Problems with O(n) solutions that are simpler and fast enough

Architecture: Boundary Finding Framework

graph TD
    A["Define predicate P(x)"] --> B["Is P(mid) true?"]
    B -->|Yes| C[Answer in left half or at mid]
    B -->|No| D[Answer in right half]
    C --> E[Move right = mid]
    D --> F[Move left = mid + 1]
    E --> B
    F --> B
    B -.->|Converge| G[Return left]

The predicate P(x) answers: “Is the answer <= x?” When this transitions from false to true exactly once, binary search finds that transition point.

Production Failure Scenarios

Failure	Cause	Mitigation
Infinite loop	Using `left < right` with `left = mid` in odd-length ranges	Use `left <= right` with proper mid calculation or `left = mid + 1`
Overflow in mid calculation	`(left + right)` can overflow in large arrays	Use `mid = left + (right - left) // 2`
Wrong boundary for first/last	Confusing lower vs upper bound logic	Draw the decision tree on paper before coding
Rotated array pivot error	Assuming known rotation count	Search both halves when target not in sorted portion

Trade-off Table

Variant	Time	Space	Key Insight
Basic Binary Search	O(log n)	O(1)	Find exact match
Lower Bound	O(log n)	O(1)	Find first >= target
Upper Bound	O(log n)	O(1)	Find first > target
Rotated Array Search	O(log n)	O(1)	Determine which half is sorted
Peak Finding	O(log n)	O(1)	Mid compares to neighbor
Fractional Search	O(log n)	O(1)	Binary search on floating answer

Implementation

Lower Bound (First Occurrence >= Target)

def lower_bound(arr, target):
    """
    Find index of first element >= target.
    Returns len(arr) if target larger than all elements.
    """
    left, right = 0, len(arr)

    while left < right:
        mid = left + (right - left) // 2

        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid

    return left

Upper Bound (First Occurrence > Target)

def upper_bound(arr, target):
    """
    Find index of first element > target.
    """
    left, right = 0, len(arr)

    while left < right:
        mid = left + (right - left) // 2

        if arr[mid] <= target:
            left = mid + 1
        else:
            right = mid

    return left

Search in Rotated Sorted Array

def search_rotated(nums, target):
    """
    Search in rotated sorted array (no duplicates).
    Returns index if found, -1 otherwise.
    """
    left, right = 0, len(nums) - 1

    while left <= right:
        mid = left + (right - left) // 2

        if nums[mid] == target:
            return mid

        # Determine which half is sorted
        if nums[left] <= nums[mid]:
            # Left half sorted
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        else:
            # Right half sorted
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1

    return -1

Fractional Search (Optimization)

def fractional_search(f, left, right, epsilon=1e-7):
    """
    Find x that maximizes f(x) where f is unimodal.
    """
    while right - left > epsilon:
        mid1 = left + (right - left) / 3
        mid2 = right - (right - left) / 3

        if f(mid1) < f(mid2):
            left = mid1
        else:
            right = mid2

    return (left + right) / 2

Common Pitfalls / Anti-Patterns

Off-by-one in termination — left < right vs left <= right changes behavior; former searches for boundary, latter for exact match
Mid calculation order — Always use left + (right - left) // 2 to prevent overflow
Confusing sorted half detection — In rotated arrays, check nums[left] <= nums[mid] not just equality
Not handling duplicates — Rotated array search with duplicates requires O(n) worst case

Quick Recap Checklist

Is the condition monotonic for binary search application?
Used overflow-safe mid calculation?
Correct termination condition (≤ vs <)?
For rotated array: confirmed which half is sorted?
Tested: empty array, single element, target at boundaries

Observability Checklist

Track binary search implementations to catch edge case failures.

Core Metrics

Search iteration count (should be O(log n))
Left/right boundary values at termination
Input size and target value
Comparison count per search

Health Signals

Iteration count exceeding O(log n) by 2x or more
Boundary values not converging (infinite loop risk)
Index values going negative or exceeding bounds

Alerting Thresholds

Iteration count > 40 for n < 1B: overflow or boundary bug
Any comparison where left > right: immediate alert
Search time p99 > 10ms for single operation: investigate

Distributed Tracing

Trace binary search with iteration count and boundary values
Include target and input size in span attributes

Security Notes

Binary search has specific security concerns.

Timing attacks on sorted data

The branching in binary search depends on comparison results. In sensitive contexts, an attacker who can measure execution time could infer whether the target is in the higher or lower half, slowly narrowing to the exact value.

Fix: Use constant-time comparison functions. In high-security contexts, consider obfuscating the search space or adding noise to timing.

Overflow in mid calculation

The mid = (left + right) // 2 calculation overflows for large left/right values in fixed-size integer languages.

Fix: Use mid = left + (right - left) // 2 universally, even in languages with arbitrary precision integers.

Interview Questions

1. How do you search in a rotated array with duplicates?

With duplicates, the worst case becomes O(n) because you can't determine which half is sorted when nums[left] == nums[mid] == nums[right]. The algorithm must fallback to linear search when this ambiguity occurs. If duplicates are guaranteed, consider sorting first or using a different approach.

2. What's the boundary-finding perspective of binary search?

Think of binary search as finding where a predicate P(x) transitions from false to true. For "first occurrence >= target", the predicate is arr[i] < target. Binary search finds the leftmost index where the predicate becomes false. This perspective handles first/last occurrence, lower/upper bound, and optimization problems uniformly.

3. How do you find the minimum in a rotated sorted array?

The minimum element is the pivot point where the sorted sequence restarts. Use binary search: if nums[mid] > nums[right], minimum is in right half (left = mid + 1). Otherwise, minimum is in left half including mid (right = mid). The answer is at nums[left] when left == right.

4. How would you find the peak element in a mountain array using binary search?

A mountain array (bitonic array) increases then decreases with exactly one peak. Use binary search: compare arr[mid] with arr[mid + 1]. If arr[mid] < arr[mid + 1], the peak is in the right half (left = mid + 1). Otherwise, the peak is in the left half including mid (right = mid). When left == right, that index is the peak.

5. How do you search in a sorted infinite array or array of unknown size?

Since binary search requires boundaries, you first determine the search range exponentially:

Start with left = 0, right = 1. Double right while arr[right] < target (or until you get an out-of-bounds indicator).
Once arr[right] >= target, perform standard binary search within [left, right].
This exponential search combined with binary search runs in O(log pos) where pos is the target position.

6. How would you find the square root of a number using binary search?

Treat it as a binary search on the answer:

Set left = 0, right = x (or x // 2 + 1 for efficiency).
While left <= right, compute mid = left + (right - left) // 2.
If mid * mid == x, return mid. If mid * mid < x, left = mid + 1. Otherwise right = mid - 1.
Return right (floor of square root). For floating-point, use abs(mid * mid - x) < epsilon.

7. Explain how to find the first bad version in a version control system using binary search.

This is the canonical first true in a monotonic predicate problem.

Define isBadVersion(n) — returns true if version n is bad. All versions after the first bad are also bad.
Use lower-bound binary search: left = 1, right = n; while left < right, if isBadVersion(mid) is false, left = mid + 1, else right = mid.
Return left — the first bad version. Time: O(log n), space: O(1).

8. How do you count occurrences of a target in a sorted array using binary search variants?

Use lower bound and upper bound together:

Find first = lower_bound(arr, target) (first index >= target).
Find last = upper_bound(arr, target) (first index > target).
Count = last - first. If arr[first] != target, count is 0.
Total time: O(log n), two binary searches. Can optimize to one search by finding any occurrence first, then expanding.

9. How do you find the floor and ceiling of a target in a sorted array?

Floor = largest element ≤ target. Ceiling = smallest element ≥ target.

Ceiling is simply lower_bound(arr, target). Return arr[lower_bound] if it exists.
Floor: compute upper_bound(arr, target), then floor is at upper_bound - 1 (if valid).
Alternatively, use modified binary search tracking the best candidate. Both run in O(log n).

10. What is binary search on the answer and when would you use it?

Binary search on the answer applies when the answer space is continuous or integer-ranged, and you can verify whether a candidate answer satisfies the problem constraints.

Key property: The feasibility function is monotonic — if answer x works, all larger (or smaller) answers also work.
Examples: Minimum capacity to ship packages within D days, smallest k such that koko can eat all bananas in H hours, square root, n-th root.
Pattern: Binary search over the answer range [lo, hi], check predicate feasible(mid), narrow until convergence. Time: O(log(range) × feasibility_check_time).

11. How do you search in a row-wise and column-wise sorted 2D matrix?

For a matrix where each row is sorted and each column is sorted, start from the top-right corner:

If matrix[row][col] == target, return true.
If matrix[row][col] > target, move left (col--) — this column is too large.
If matrix[row][col] < target, move down (row++) — this row is too small.
Time: O(m + n). Cannot use binary search on both dimensions simultaneously because the monotonic property does not hold in 2D.

12. Find the index where the sum of left elements equals the sum of right elements (equilibrium index).

Use binary search on the prefix sum concept:

Compute total sum, then iterate with left_sum = 0, right_sum = total - arr[i].
If left_sum == right_sum, return i. Update left_sum += arr[i] each step.
Binary search variant: for monotonic checking, use total - left_sum - arr[mid] vs left_sum to decide which side to search. Time: O(log n) if array is monotonic, O(n) for general case since prefix sums are not monotonic.

13. How do you find the position to insert an element in a sorted array to maintain sorted order?

Use bisect functions or implement lower/upper bound:

bisect_left returns index of first element >= target (lower bound). Use for insertion that keeps sorted.
bisect_right returns index of first element > target (upper bound). Use when you want all equal elements grouped at insertion point.
Implementation: binary search with left < right loop; arr[mid] < target means go right, else go left. Return left.
Edge cases: insert at beginning (returns 0), insert at end (returns len(arr)).

14. Find the minimum days to ship all packages given a daily capacity (LeetCode 1011).

Classic binary search on answer: the minimum capacity is between max(weights) and sum(weights).

Predicate: can ship all packages in D days with capacity C? Simulate: accumulate weights, split when daily_sum exceeds C.
Binary search over [max(arr), sum(arr)]. For mid, count required days. If days > D, increase capacity; else decrease.
Time: O(n log(sum - max(arr))). Space: O(1).

15. Find the minimum element in a rotated sorted array with duplicates — how does it change the algorithm?

With duplicates, worst-case becomes O(n). The standard algorithm:

If nums[mid] > nums[right], minimum in right half (left = mid + 1).
If nums[mid] < nums[right], minimum in left half (right = mid).
If nums[mid] == nums[right], you cannot decide — decrement right by one and continue. This handles duplicates.
When duplicates are prevalent, linear search may be needed in the worst case.

16. How do you find a target in a bitonic array (strictly increasing then strictly decreasing)?

Use binary search in two phases: first find the peak, then search each half.

Find peak: compare arr[mid] with arr[mid+1]. If increasing, left = mid + 1; else right = mid.
After peak is found (left == right), binary search left half (0 to peak) with increasing condition.
Binary search right half (peak to n-1) with decreasing condition (treat as reversed sorted or use reverse comparison).
Time: O(log n) for finding peak + O(log n) for search = O(log n) total.

17. How do you find the kth smallest element in the union of two sorted arrays?

Use binary search on the answer or median-of-medians approach:

Binary search on value range: let low = max(arr1[0], arr2[0]), high = min(arr1[-1], arr2[-1]).
Count elements <= mid in both arrays using lower_bound. If count >= k, high = mid; else low = mid + 1.
Alternative: use two-pointer approach starting from k/2 in each array. Time: O(log k) for binary search, O(k) for pointer approach.

18. Find the median of two sorted arrays (LeetCode 4) — when should you use binary search versus divide and conquer?

Use binary search on partition: partition array1 at index i and array2 at index j such that:

i + j = (len1 + len2 + 1) // 2 for median (including even/odd handling).
Elements left of partition <= elements right of partition. Binary search on i (or j) to find valid partition.
If arr1[i-1] <= arr2[j] and arr2[j-1] <= arr1[i], partition is correct. Median is max(left) and min(right).
Time: O(log(min(len1, len2))). Space: O(1). This is preferred over merge (O(n) time, O(n) space).

19. When would you use lower bound versus upper bound — what's the practical difference?

Lower bound finds first position where value >= target; upper bound finds first position where value > target.

Lower bound: use when you need the insertion point that keeps sorted order, or first occurrence. Example: find first bad version, first position to place an element.
Upper bound: use when you need the position after all equal elements, or for counting occurrences (upper - lower gives count).
Implementation difference: lower checks arr[mid] < target, upper checks arr[mid] <= target. The = in upper bound skips equal elements.

20. What are the most common bugs when implementing binary search and how do you avoid them?

Critical bugs that cause incorrect results or infinite loops:

Infinite loop: left = mid without +1 when using left < right. Fix: use left = mid + 1 or right = mid - 1.
Overflow: mid = (left + right) // 2 overflows for large values. Fix: mid = left + (right - left) // 2.
Off-by-one at boundaries: wrong termination condition. left <= right for exact match; left < right for boundary finding.
Wrong half selection: when comparing arr[mid] to target, ensure direction is correct for the predicate.
Always test with: empty array, single element, target at both ends, target not in array.

Conclusion

Binary search is really about finding the boundary between true and false—once you see it that way, all the variants click. Lower bound finds the first index where arr[i] >= target; upper bound finds the first arr[i] > target. Rotated sorted arrays require checking which half is sorted before deciding which side to search. The boundary-finding lens handles optimization problems too: fractional search on continuous answer spaces uses ternary search rather than binary, but the same eliminate-half-of-search-space logic applies. Common pitfalls: use left + (right - left) // 2 to avoid overflow, and know your termination condition—left < right for boundaries, left <= right for exact match.

Binary Search Variants: Beyond Simple Lookup

Introduction

When to Use

When Not to Use

Architecture: Boundary Finding Framework

Production Failure Scenarios

Trade-off Table

Implementation

Lower Bound (First Occurrence >= Target)

Upper Bound (First Occurrence > Target)

Search in Rotated Sorted Array

Fractional Search (Optimization)

Common Pitfalls / Anti-Patterns

Quick Recap Checklist

Observability Checklist

Core Metrics

Health Signals

Alerting Thresholds

Distributed Tracing

Security Notes

Timing attacks on sorted data

Overflow in mid calculation

Interview Questions

Further Reading

Conclusion

Category

Tags

Related Posts

Bit Manipulation: Power of Bits

Common Coding Interview Patterns

Divide and Conquer: Breaking Problems into Subproblems