Bugs के बिना Classic Binary Search

द्विआधारी खोज क्रमबद्ध सूची में प्रत्येक चरण पर परास को आधा करके कोई मान खोजती है। इससे धीमी O(n) जाँच तेज़ O(log n) खोज में बदल जाती है।

द्विआधारी खोज केवल क्रमबद्ध डेटा पर काम करती है। यदि सूची अक्रमबद्ध है, तो पहले उसे sort करें, वरना परिणाम निरर्थक और गलत होगा।

दो संकेतकों से शुरू करें: low अनुक्रमांक 0 पर और high अंतिम अनुक्रमांक पर। यदि लक्षित मान मौजूद है, तो वह हमेशा इनके बीच होगा।

mid को low + (high - low) // 2 के रूप में निकालें। Python में अतिप्रवाह समस्या नहीं है, लेकिन यह रूप हर जगह सुरक्षित आदत है।

a[mid] की तुलना लक्ष्य से करें। या तो आपने उसे खोज लिया, वह बहुत छोटा है, या बहुत बड़ा है। प्रत्येक स्थिति परास को अलग तरह से छोटा करती है।

यदि a[mid] लक्ष्य से छोटा है, तो उत्तर दाईं ओर ही होगा। low को mid + 1 पर ले जाएँ और बाएँ आधे हिस्से को हटा दें।

यदि a[mid] लक्ष्य से बड़ा है, तो बाएँ आधे हिस्से में खोजें। high को mid - 1 पर ले जाएँ, ताकि mid की दोबारा जाँच न हो।

जब तक low, high से छोटा या उसके बराबर हो, तब तक आगे बढ़ते रहें। जब दोनों एक-दूसरे को पार कर जाते हैं, तो परास खाली होता है और लक्ष्य मौजूद नहीं होता।

यदि लूप बिना मिलान के समाप्त हो जाए, तो मान मौजूद नहीं है। परंपरा के अनुसार -1 लौटाएँ, ताकि कॉल करने वाला सफलता और विफलता में अंतर कर सके।

सामान्य गलती संकेतक को आगे बढ़ाते समय +1 या -1 भूल जाना है। इसे छोड़ देने पर mid की जाँच हमेशा दोहरती रहती है और अनंत लूप बन जाता है।

साधारण सदस्यता-जाँच के लिए Python का bisect मॉड्यूल पहले से ही त्रुटिरहित खोज देता है। केवल तभी लूप स्वयं लिखें जब आपको विशेष तर्क चाहिए।

अब आप low और high निर्धारित कर सकते हैं, mid को सुरक्षित रूप से निकाल सकते हैं, सही हिस्से को छोटा कर सकते हैं और एक-से-अधिक की गलती से बच सकते हैं। लघुगणकीय खोज अब आपकी है। 🎯