Binary Search Algorithm Variations and Their Edge Cases: A Complete Guide to the LeetCode Repository

Binary search algorithm variations include standard value search, leftmost/rightmost insertion (bisect-left/right), ability-test predicate search, and virtual space search, each requiring careful handling of edge cases like empty inputs, integer overflow, and duplicate elements.

The azl397985856/leetcode repository provides a comprehensive thinking series that breaks binary search into reusable templates. According to the source analysis in thinkings/binary-search-1.en.md and thinkings/binary-search-2.en.md, mastering binary search algorithm variations and their edge cases requires understanding seven distinct patterns and six critical failure modes.

Core Binary Search Variations in the LeetCode Repository

Standard Value Search

The classic pattern searches for an exact target in a sorted array using a closed interval [l, r]. As implemented in thinkings/binary-search-2.en.md, the loop runs while l <= r, computing mid = l + (r - l) // 2 to avoid overflow.

def binary_search(nums, target):
    l, r = 0, len(nums) - 1
    while l <= r:
        mid = l + (r - l) // 2
        if nums[mid] == target:
            return mid
        if nums[mid] < target:
            l = mid + 1
        else:
            r = mid - 1
    return -1

Leftmost Insertion (Bisect-Left)

This variation finds the first position where target could be inserted to maintain order. According to thinkings/binary-search-2.en.md, the key difference is the condition if nums[mid] >= target: r = mid - 1, which ensures the search continues leftward even on equality.

def bisect_left(nums, x):
    l, r = 0, len(nums) - 1
    while l <= r:
        mid = (l + r) // 2
        if nums[mid] >= x:
            r = mid - 1
        else:
            l = mid + 1
    return l

Rightmost Insertion (Bisect-Right)

The rightmost insertion finds the position after the last occurrence of target. The implementation in thinkings/binary-search-2.en.md uses if nums[mid] > target: r = mid - 1 else: l = mid + 1, moving left on strictly greater values only.

Find-or-Insert Combined Pattern

This hybrid approach uses leftmost insertion followed by an equality check. As shown in the repository's templates, it returns the index if found, otherwise -1 or the insertion point, depending on requirements.

def find_or_insert(nums, target):
    idx = bisect_left(nums, target)
    if idx < len(nums) and nums[idx] == target:
        return idx
    return -1

Ability-Test (Predicate) Binary Search

The ability-test pattern searches for the smallest (or largest) value satisfying a monotonic predicate possible(mid). This variation appears in problems like "Capacity To Ship Packages Within D Days" (problems/1011.capacity-to-ship-packages-within-d-days-en.md) and "Koko Eating Bananas" (LeetCode 875).

def min_eating_speed(piles, H):
    def possible(k):
        return sum((p + k - 1) // k for p in piles) <= H

    l, r = 1, max(piles)
    while l <= r:
        mid = (l + r) // 2
        if possible(mid):
            r = mid - 1
        else:
            l = mid + 1
    return l

Counting via Two-Point Binary

To count occurrences of a value in a sorted array, compute the difference between rightmost and leftmost insertion points. As noted in thinkings/binary-search-2.en.md, this achieves O(log n) time complexity.

def count_occurrences(nums, x):
    return bisect_right(nums, x) - bisect_left(nums, x)

Binary Search on Virtual Space

This advanced variation applies binary search to a derived monotonic function rather than the original array. Examples include searching for the k-th smallest pair distance or finding the maximum distance to place magnetic balls. The search operates on the range of possible answers, with a predicate function counting how many elements satisfy the current mid-value.

Critical Edge Cases and Implementation Pitfalls

Empty Input Arrays

When nums is empty, the standard search must return -1 immediately. For insertion variants, bisect_left and bisect_right should return 0, representing insertion at the beginning.

Target Values Outside the Range

If all elements are smaller than target, leftmost insertion returns len(nums). If all elements are larger, it returns 0. Implementation must handle these bounds without index errors.

Handling Duplicate Elements

Duplicates require careful boundary movement. For leftmost insertion, use nums[mid] >= target to shrink the right bound on equality. For rightmost insertion, use nums[mid] > target to shrink the right bound only on strictly greater values, allowing the left bound to move past duplicates.

Integer Overflow in Midpoint Calculation

Calculating mid as (l + r) // 2 risks overflow in languages with fixed-size integers. The repository consistently uses mid = l + (r - l) // 2 to prevent this error.

Open vs. Closed Interval Consistency

Mixing interval types causes off-by-one bugs. The LeetCode repository templates use closed intervals [l, r] with the loop condition while l <= r. Changing to half-open [l, r) requires adjusting boundary updates and termination conditions.

Monotonicity Violations in Predicate Search

The ability-test pattern assumes a monotonic predicate: if possible(mid) is true, all values greater than mid are also true (or vice versa). Applying binary search to non-monotonic functions results in infinite loops or incorrect answers.

Summary

• Binary search algorithm variations in the LeetCode repository include standard value search, leftmost/rightmost insertion (bisect-left/right), find-or-insert patterns, ability-test predicate search, counting via two-point binary, and virtual space search.
• Closed interval [l, r] with while l <= r is the canonical template used across thinkings/binary-search-1.en.md and thinkings/binary-search-2.en.md.
• Safe midpoint calculation using mid = l + (r - l) // 2 prevents integer overflow.
• Edge cases requiring explicit handling include empty arrays, targets outside the value range, duplicate elements, and monotonicity violations in predicate-based searches.

Frequently Asked Questions

What is the difference between bisect-left and bisect-right in binary search?

Bisect-left finds the first position where a target can be inserted to maintain order, returning the leftmost index of duplicates. Bisect-right finds the position after the last occurrence of the target, effectively returning the insertion point to the right of duplicates. In the LeetCode repository's thinkings/binary-search-2.en.md, bisect-left uses the condition nums[mid] >= target while bisect-right uses nums[mid] > target to handle these boundary differences.

How do I avoid integer overflow when calculating the midpoint in binary search?

To avoid integer overflow, calculate the midpoint using mid = left + (right - left) // 2 instead of (left + right) // 2. This is particularly important in languages with fixed-size integers like C++ or Java where left + right could exceed the maximum integer value. The LeetCode repository consistently applies this pattern in thinkings/binary-search-2.en.md to ensure safe midpoint computation across all binary search variations.

When should I use the ability-test (predicate) binary search pattern?

Use the ability-test pattern when searching for the smallest or largest value that satisfies a specific condition (predicate) rather than searching for a specific value in an array. This pattern appears in problems like "Capacity To Ship Packages Within D Days" (problems/1011.capacity-to-ship-packages-within-d-days-en.md) and "Koko Eating Bananas" (LeetCode 875), where you binary search on the range of possible answers (e.g., eating speeds or ship capacities) and use a helper function to test if a given value is feasible.

How do I handle duplicate elements in binary search?

Handling duplicates requires adjusting your comparison logic to continue searching even after finding an equal value. For leftmost insertion, use if nums[mid] >= target: r = mid - 1 to keep moving left when equal, ensuring you find the first occurrence. For rightmost insertion, use if nums[mid] > target: r = mid - 1 else: l = mid + 1 to move right past equals. As documented in thinkings/binary-search-2.en.md, these boundary adjustments prevent premature termination on duplicates and ensure correct insertion points for counting occurrences via bisect_right - bisect_left.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}