पायथन में bisect: ऐरे बाइसेक्शन एल्गोरिदम

bisect मॉड्यूल सॉर्टेड लिस्ट में इंसर्शन पॉइंट ढूंढने और सॉर्टेड ऑर्डर बनाए रखते हुए इंसर्ट करने के लिए बाइनरी सर्च (बाइसेक्शन) एल्गोरिदम प्रदान करता है। O(log n) सर्च, O(n) इंसर्शन (लिस्ट शिफ्ट के कारण)।

मुख्य फ़ंक्शन्स

bisect_left(a, x, lo=0, hi=len(a))

इंसर्शन पॉइंट लौटाता है पहले किसी मौजूदा एंट्री के (बाएं)।

bisect_right(a, x, lo=0, hi=len(a))

इंसर्शन पॉइंट लौटाता है बाद किसी मौजूदा एंट्री के (दाएं)। bisect इसका एलियास है।

insort_left(a, x, lo=0, hi=len(a))

x को सॉर्टेड ऑर्डर में इंसर्ट करता है (बाएं)।

insort_right(a, x, lo=0, hi=len(a))

x को सॉर्टेड ऑर्डर में इंसर्ट करता है (दाएं)। insort इसका एलियास है।

उदाहरण

import bisect

nums = [45, 21, 34, 87, 56, 12, 5, 98, 30, 63]
nums.sort()
print(nums)  # [5, 12, 21, 30, 34, 45, 56, 63, 87, 98]

# इंसर्शन पॉइंट ढूंढें
pos = bisect.bisect_left(nums, 50)
print(pos)  # 6

# इंसर्ट करें
nums.insert(pos, 50)
print(nums)  # [5, 12, 21, 30, 34, 45, 50, 56, 63, 87, 98]

# insort उपयोग करें (ढूंढना + इंसर्ट एक साथ)
bisect.insort(nums, 29)
print(nums)  # [5, 12, 21, 29, 30, 34, 45, 50, 56, 63, 87, 98]

# डुप्लिकेट्स के साथ
bisect.insort_left(nums, 30)
bisect.insort_right(nums, 30)
print(nums)  # ... 29, 30, 30, 30, 34 ...

व्यावहारिक उपयोग केस

1. सॉर्टेड लिस्ट मेंटेन करना

# लॉग एंट्रीज़ को टाइमस्टैम्प द्वारा सॉर्टेड रखना
logs = []
bisect.insort(logs, (timestamp, message))

2. रेंज क्वेरीज़

# मानों की रेंज में काउंट
left = bisect.bisect_left(nums, 20)
right = bisect.bisect_right(nums, 60)
count = right - left
print(f"20 से 60 के बीच {count} मान")

3. परसेंटाइल/मीडियन

def median(sorted_list):
    n = len(sorted_list)
    if n % 2 == 1:
        return sorted_list[n // 2]
    else:
        return (sorted_list[n//2 - 1] + sorted_list[n//2]) / 2

महत्वपूर्ण नोट्स

• लिस्ट पहले से सॉर्टेड होनी चाहिए - मॉड्यूल चेक नहीं करता।
• lo, hi पैरामीटर्स से सब-स्लाइस सर्च कर सकते हैं।
• कस्टम की फ़ंक्शन के लिए bisect सीधे सपोर्ट नहीं करता - की-ट्रांसफॉर्म्ड लिस्ट उपयोग करें या bisect_left को की-एक्सट्रैक्शन के साथ कस्टमाइज़ करें।
• बड़े डेटासेट्स के लिए जहां बार-बार इंसर्शन/डिलीशन हो, blist या sortedcontainers (थर्ड-पार्टी) बेहतर हैं।

जटिलता