Binary Search Optimization Patterns

Optimizations are usually about removing linear scans inside check (using heaps, sorted structures, or precomputation) so overall stays O(n log n) or better.

Try this in Python

import bisect


def count_pairs_with_diff_at_least(nums_sorted: list[int], d: int) -> int:
    """Count pairs i<j with nums[j]-nums[i] >= d (two-pointer often wins; here bisect demo)."""
    nums_sorted.sort()
    c = 0
    for i, x in enumerate(nums_sorted):
        j = bisect.bisect_left(nums_sorted, x + d, lo=i + 1)
        c += len(nums_sorted) - j
    return c


a = [1, 4, 6, 10]
print(count_pairs_with_diff_at_least(a, 3))

Key takeaways

• bisect in Python is binary search utilities—learn it.
• Choose the right tool: sometimes two pointers beat binary search.
• Profile the expensive part of check.