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

> Master binary search variations like bisect_left/right and predicate search. Handle edge cases: empty inputs, overflow, duplicates. Your LeetCode guide.

- Repository: [lucifer/leetcode](https://github.com/azl397985856/leetcode)
- Tags: deep-dive
- Published: 2026-03-06

---

**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`](https://github.com/azl397985856/leetcode/blob/main/thinkings/binary-search-1.en.md) and [`thinkings/binary-search-2.en.md`](https://github.com/azl397985856/leetcode/blob/main/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`](https://github.com/azl397985856/leetcode/blob/main/thinkings/binary-search-2.en.md), the loop runs while `l <= r`, computing `mid = l + (r - l) // 2` to avoid overflow.

```python
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`](https://github.com/azl397985856/leetcode/blob/main/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.

```python
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`](https://github.com/azl397985856/leetcode/blob/main/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.

```python
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`](https://github.com/azl397985856/leetcode/blob/main/problems/1011.capacity-to-ship-packages-within-d-days-en.md)) and "Koko Eating Bananas" (LeetCode 875).

```python
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`](https://github.com/azl397985856/leetcode/blob/main/thinkings/binary-search-2.en.md), this achieves `O(log n)` time complexity.

```python
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`](https://github.com/azl397985856/leetcode/blob/main/thinkings/binary-search-1.en.md) and [`thinkings/binary-search-2.en.md`](https://github.com/azl397985856/leetcode/blob/main/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`](https://github.com/azl397985856/leetcode/blob/main/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`](https://github.com/azl397985856/leetcode/blob/main/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`](https://github.com/azl397985856/leetcode/blob/main/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`](https://github.com/azl397985856/leetcode/blob/main/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`.