बाइनरी सर्च
क्रमबद्ध ऐरे में मान ढूँढता है: बीच में देखता है और वह आधा हिस्सा फेंक देता है जिसमें मान नहीं हो सकता। हर तुलना बचे हिस्से को आधा कर देती है।
- सर्वश्रेष्ठ Ω(1)
- Θ(log n)
- सबसे खराब O(log n)
- मेमोरी O(1)
log₂ n: n को कितनी बार आधा किया जा सकता है जब तक 1 न बचे। 64 मानों के लिए यह 6 है, यानी अधिकतम 7 तुलनाएं।
इस पेज के अन्य शब्द
- क्रमबद्ध: बढ़ते क्रम में। बाइनरी सर्च को इसकी ज़रूरत है; बिना क्रम वाले डेटा पर यह गलत जवाब देता है।
- आधा करना: हर तुलना बचे हिस्से का आधा फेंक देती है, वह आधा जिसमें लक्ष्य नहीं हो सकता।
- बीच (mid)
- मिला
- बाहर
- लक्ष्य
इसे आज़माएं: ऐसा लक्ष्य चुनें जो ऐरे में नहीं है। खोज फिर भी अधिकतम ⌈log₂(n + 1)⌉ तुलनाओं के बाद रुक जाती है, जब lo, hi से आगे निकल जाता है।
यह कैसे काम करता है
बाइनरी सर्च ऐरे के उस हिस्से के चारों ओर दो निशान, lo और hi, रखता है जहाँ लक्ष्य अभी भी हो सकता है। यह बीच वाले मान को देखता है: अगर वही लक्ष्य है, तो काम खत्म; अगर वह छोटा है, तो लक्ष्य सिर्फ़ दाईं ओर हो सकता है, इसलिए lo बीच के आगे चला जाता है; अगर बड़ा है, तो hi बीच के पहले आ जाता है। हर कदम बचे हिस्से को आधा करता है: 64 मानों के लिए अधिकतम 7 तुलनाएं, दस लाख के लिए अधिकतम 20। जब lo, hi से आगे निकल जाता है, तो कुछ नहीं बचता: मान ऐरे में नहीं है।
यह कब सही विकल्प है
जब भी डेटा क्रमबद्ध हो और किसी भी स्थान पर सीधे जा सकें, बाइनरी सर्च इस्तेमाल करें: क्रमबद्ध सूची में शब्द, रिलीज़ इतिहास में संस्करण, git bisect, क्रमबद्ध ऐरे में डालने की जगह। बिना क्रम वाले डेटा पर यह गलत जवाब देता है, और पहले क्रमबद्ध करना तभी फ़ायदेमंद है जब कई बार खोजना हो।