बाइनरी सर्च

बाइनरी सर्च वैसे ही काम करता है जैसे आप शब्दकोश में कोई शब्द ढूँढते हैं: उसे बीच से खोलें, देखें कि शब्द पहले आता है या बाद में, और उस आधे हिस्से के साथ दोहराएँ। सॉर्ट की हुई सूची में यह दस लाख मानों में से कोई भी मान ज़्यादा से ज़्यादा 20 तुलनाओं में ढूँढ लेता है।

सॉर्ट किए हुए बार की एक पंक्ति, जिसमें बीच वाला बार हाइलाइट है, पंक्ति का आधा हिस्सा धुंधला है, और लक्ष्य की ऊँचाई पर एक डैश वाली रेखा है
सॉर्ट किए हुए बार की एक पंक्ति, जिसमें बीच वाला बार हाइलाइट है, पंक्ति का आधा हिस्सा धुंधला है, और लक्ष्य की ऊँचाई पर एक डैश वाली रेखा है

मूल विचार

सॉर्ट की हुई सूची में एक तुलना सिर्फ़ यह नहीं बताती कि लक्ष्य मिला या नहीं: यह भी बताती है कि लक्ष्य किस तरफ़ है। लक्ष्य की तुलना बीच वाले मान से करें। बराबर हों तो काम पूरा। अगर बीच का मान छोटा है, तो उससे पहले के सभी मान भी छोटे हैं, इसलिए लक्ष्य सिर्फ़ उसके बाद हो सकता है। अगर बड़ा है, तो लक्ष्य सिर्फ़ उसके पहले हो सकता है। सिर्फ़ वह आधा रखें और दोहराएँ।

एक उदाहरण

2, 5, 8, 12, 16, 23, 38, 56, 72, 91 में 23 खोजें। बीच का मान 16 है, जो छोटा है, इसलिए सिर्फ़ 23 से 91 बचते हैं। उनका बीच 56 है, जो बड़ा है, इसलिए सिर्फ़ 23 और 38 बचते हैं। उनका बीच 23 है: 3 तुलनाओं के बाद स्थान 6 पर मिल गया, जबकि लीनियर सर्च को 6 चाहिए। इसी सूची में 40 खोजने पर 16, 56, 23 और 38 से तुलना होती है, जिसके बाद कुछ नहीं बचता: यह जानने में 4 तुलनाएँ लगती हैं कि 40 मौजूद नहीं है, जबकि लीनियर सर्च को 10 लगती हैं।

आधा करते-करते जल्दी घटता है

एक तुलना के बाद ज़्यादा से ज़्यादा आधी सूची बचती है, दो के बाद एक-चौथाई, k के बाद ज़्यादा से ज़्यादा लगभग n/2ᵏ। सर्च तब रुकता है जब कुछ न बचे, इसलिए इसे ज़्यादा से ज़्यादा ⌊log₂ n⌋ + 1 तुलनाएँ चाहिए: 40 मानों के लिए 6, 1,000 के लिए 10, दस लाख के लिए 20 और एक अरब के लिए 30। सूची दोगुनी करने पर बस एक तुलना बढ़ती है। इसे O(log n) लिखा जाता है।

बताना आसान, सही लिखना मुश्किल

John Mauchly ने 1946 में बाइनरी सर्च का वर्णन किया, लेकिन Donald Knuth के अनुसार हर लंबाई की सूची पर सही चलने वाला पहला संस्करण 1962 तक प्रकाशित नहीं हुआ। बाद में Jon Bentley ने पाया कि लगभग दस में से एक पेशेवर प्रोग्रामर ही इसे सही लिख पाया: अंत की शर्तें और आधे करते समय एक जोड़ना या घटाना आसानी से ग़लत हो जाते हैं। 2006 में Joshua Bloch ने दिखाया कि बीच निकालने का आम तरीका, (low + high) / 2, बहुत लंबी सूचियों में ओवरफ़्लो कर सकता है, एक ऐसा बग जो Java लाइब्रेरी में सालों तक रहा। इस ऐप की तरह low + (high − low) / 2 लिखने से यह बचता है।

अमेरिकी सेना की एक तस्वीर में ENIAC के सामने ENIAC के अन्य अधिकारियों के साथ जॉन मॉकली (बाएँ से पाँचवें)। मॉकली ने 1946 में बाइनरी सर्च का वर्णन किया।
अमेरिकी सेना की एक तस्वीर में ENIAC के सामने ENIAC के अन्य अधिकारियों के साथ जॉन मॉकली (बाएँ से पाँचवें)। मॉकली ने 1946 में बाइनरी सर्च का वर्णन किया।

रूप और उपयोग

डुप्लिकेट होने पर बाइनरी सर्च मिलानों में से कोई एक ढूँढता है; जो संस्करण बाएँ या दाएँ चलते रहते हैं, वे पहला या आख़िरी मिलान ढूँढते हैं, या वह जगह जहाँ कोई ग़ायब मान डाला जाएगा। आधा करने का यही विचार किसी समीकरण का मूल ढूँढता है (बाइसेक्शन), वह संस्करण ढूँढता है जिसमें कोई बग पहली बार आया (git bisect), और कई ऑप्टिमाइज़ेशन पहेलियों का उत्तर भी। बाइनरी सर्च ट्री डेटा को ऐसे रखते हैं कि हर खोज आधा करने वाले उसी रास्ते पर चलती है।

इसे आज़माएँ

ऐप खोलें, खोजें में कोई मान चुनें, और आगे दबाएँ। छायांकित हिस्सा वह है जहाँ लक्ष्य अब भी हो सकता है; बीच का मान हाइलाइट होता है, और हटाया गया आधा हिस्सा धुंधला हो जाता है। टाइलें दिखाती हैं कि कितने मान अब भी संभव हैं और उसी मान के लिए लीनियर सर्च को कितनी तुलनाएँ चाहिए। अंतर बढ़ता देखने के लिए कोई ग़ायब मान खोजें, या 40 बार इस्तेमाल करें।

अक्सर पूछे जाने वाले प्रश्न

बाइनरी सर्च की टाइम कॉम्प्लेक्सिटी क्या है?

O(log n): n मानों के लिए ज़्यादा से ज़्यादा ⌊log₂ n⌋ + 1 तुलनाएँ। सबसे अच्छी स्थिति एक तुलना है, जब लक्ष्य बीच में हो। इटरेटिव संस्करण को O(1) अतिरिक्त मेमोरी चाहिए।

बाइनरी सर्च और लीनियर सर्च में क्या अंतर है?

लीनियर सर्च हर मान को बारी-बारी से जाँचता है और किसी भी सूची पर काम करता है, लेकिन उसे n तुलनाएँ लग सकती हैं। बाइनरी सर्च सिर्फ़ सॉर्ट की हुई सूची पर काम करता है, लेकिन हर तुलना में बचे हुए का आधा हिस्सा हटा देता है, इसलिए उसे लगभग log₂ n तुलनाएँ चाहिए।

क्या सिर्फ़ बाइनरी सर्च के लिए सूची सॉर्ट करना फ़ायदेमंद है?

सिर्फ़ तब, जब आप उसमें कई बार खोजें। सॉर्ट करने में लगभग n log n चरण लगते हैं, जो एक लीनियर सर्च से ज़्यादा है। सूची सॉर्ट हो जाने के बाद हर अगली खोज बहुत सस्ती होती है।

क्या बाइनरी सर्च सूचियों के अलावा दूसरी चीज़ों पर काम कर सकता है?

हाँ, हर उस चीज़ पर जहाँ कोई जाँच बता दे कि आप उत्तर के किस तरफ़ हैं: संख्याओं की कोई रेंज, किसी प्रोग्राम के संस्करण, या बड़ा-छोटा अनुमान वाले खेल के अनुमान।

आज़माने के लिए तैयार?

अपने ब्राउज़र में PictorX खोलें — शुरू करने के लिए इंस्टॉल या क्रेडिट कार्ड की ज़रूरत नहीं।

बाइनरी सर्च आज़माएँ