Binary Search Optimization patterns

check-க்குள் linear scan-ஐ heap / sorted structure / preprocessing மூலம் குறைத்து overall complexity கட்டுப்படுத்துதல்.

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

• Python bisect library பயன்பாடு.
• சில நேரங்களில் two pointers சிறந்தது.
• check-ன் expensive பகுதியைப் பார்.