मैं एक-तुलना-प्रति-पुनरावृत्ति बाइनरी खोज को बेहतर ढंग से कैसे समझ सकता हूं?

Question

एक तुलना-प्रति-पुनरावृत्ति बाइनरी खोज का बिंदु क्या है? और क्या आप समझा सकते हैं कि यह कैसे काम करता है?

Answer 1

प्रति पुनरावृत्ति के साथ एक तुलना के साथ बाइनरी खोज के दो कारण हैं। कम महत्वपूर्ण प्रदर्शन है। दो प्रति पुनरावृत्ति की तुलना में शुरुआती मैच का पता लगाने से लूप का औसत एक पुनरावृत्ति बचाता है, जबकि (मानते हुए तुलना में महत्वपूर्ण काम शामिल है) एक प्रति बाइनरी खोज प्रति पुनरावृत्ति की तुलना में लगभग प्रति पुनरावृत्ति के काम को कम करता है।

बाइनरी पूर्णांक की एक सरणी खोज रहा है, तो शायद यह थोड़ा अंतर बनाता है। यहां तक ​​कि काफी महंगी तुलना के साथ, असम्बद्ध रूप से प्रदर्शन समान है, और आधा-से-कम-से-कम संभवतः अधिकतर मामलों में पीछा करने योग्य नहीं है। इसके अलावा, महंगी तुलना अक्सर उन कार्यों के रूप में कोडित होती है जो <, == या > के लिए नकारात्मक, शून्य या सकारात्मक लौटती हैं, ताकि आप दोनों की तुलना किसी भी कीमत के लिए तुलना कर सकें।

प्रति पुनरावृत्ति के साथ एक तुलना के साथ द्विआधारी खोज करने का महत्वपूर्ण कारण है क्योंकि आप केवल कुछ-बराबर-मैच से अधिक उपयोगी परिणाम प्राप्त कर सकते हैं। मुख्य खोजें आप कर सकते हैं ...

• प्रथम कुंजी> लक्ष्य
• प्रथम कुंजी> = लक्ष्य
• प्रथम कुंजी == लक्ष्य
• अंतिम कुंजी < लक्ष्य
• अंतिम कुंजी < = लक्ष्य
• अंतिम कुंजी == लक्ष्य

ये सभी एक ही मूल एल्गोरिदम को कम करते हैं। इस अच्छी तरह से पर्याप्त को समझना कि आप आसानी से सभी प्रकारों को कोड कर सकते हैं, यह मुश्किल नहीं है, लेकिन मेरे पास वास्तव में एक अच्छा स्पष्टीकरण नहीं देखा - केवल छद्म कोड और गणितीय सबूत। यह एक स्पष्टीकरण पर मेरा प्रयास है।

ऐसे गेम हैं जहां विचार को पर बिना किसी आउटशूट के लक्ष्य के करीब जितना संभव हो सके। इसे "अंडरशूटिंग" में बदलें, और यही वह है " पहले>" करता है। खोज के दौरान किसी चरण में पर्वतमाला पर विचार करें ...

| lower bound  | goal     | upper bound 
+-----------------+-------------------------+-------------- 
|   Illegal | better   worse | 
+-----------------+-------------------------+-------------- 

वर्तमान के बीच सीमा ऊपरी और अभी भी बाध्य निचले की खोज करने की आवश्यकता है। हमारा लक्ष्य कहीं भी (सामान्यतः) है, लेकिन हम अभी तक नहीं जानते हैं कि कहां है। ऊपरी सीमा से ऊपर की वस्तुओं के बारे में दिलचस्प बिंदु यह है कि वे में कानूनी हैं कि वे लक्ष्य से अधिक हैं। हम कह सकते हैं कि वर्तमान ऊपरी सीमा से ऊपर आइटम हमारे सर्वोत्तम-दूर-दूर समाधान है। हम को भी बहुत शुरुआत में कह सकते हैं, भले ही उस स्थिति में कोई आइटम न हो - अर्थ में, यदि कोई वैध इन-रेंज समाधान नहीं है, तो सबसे अच्छा समाधान है कि अस्वीकृत नहीं किया गया है ऊपरी बाउंड

प्रत्येक पुनरावृत्ति पर, हम ऊपरी और निचले बाउंड के बीच तुलना करने के लिए एक आइटम चुनते हैं। बाइनरी खोज के लिए, यह एक गोलाकार आधा रास्ता आइटम है। बाइनरी पेड़ की खोज के लिए, यह पेड़ की संरचना द्वारा निर्धारित है। सिद्धांत एक ही रास्ता है।

चूंकि हम अपने लक्ष्य से अधिक आइटम की खोज कर रहे हैं, हम परीक्षण आइटम Item [testpos] > goal का उपयोग करके तुलना करें। यदि परिणाम गलत है, तो हमारे पास ओवरशॉट (या अंडरशॉट) हमारा लक्ष्य है, इसलिए हम अपने मौजूदा सर्वोत्तम-दूर-दूर समाधान को रखते हैं, और को हमारे निचले बाउंड ऊपर समायोजित करते हैं। यदि परिणाम सत्य है, तो हमें एक नया सबसे अच्छा समाधान मिला है, इसलिए हम इसे प्रतिबिंबित करने के लिए ऊपरी बाउंड को समायोजित करते हैं।

किसी भी तरह से, हम कभी भी उस परीक्षण आइटम की तुलना कभी नहीं करना चाहते हैं, इसलिए हम अपने को सीमा से खोज करने के लिए परीक्षण आइटम को केवल (केवल तभी) को समायोजित करने के लिए बाध्य करते हैं। होने के कारण आमतौर पर अनंत लूप में परिणाम होता है।

आम तौर पर, आधे खुली श्रेणियों का उपयोग किया जाता है - एक समावेशी निचली बाध्य और एक विशेष ऊपरी सीमा। इस प्रणाली का उपयोग करते हुए, ऊपरी बाउंड इंडेक्स पर आइटम खोज सीमा (कम से कम अब नहीं) में नहीं है, लेकिन यह सबसे अच्छा समाधान है। जब आप निचले बाउंड अप को ले जाते हैं, तो आप इसे testpos+1 पर ले जाते हैं (उस आइटम को बाहर करने के लिए जो आप केवल श्रेणी से परीक्षण करते हैं)। जब आप ऊपरी बाउंड डाउन ले जाते हैं, तो आप इसे टेस्टोज़ पर ले जाते हैं (ऊपरी बाउंड वैसे भी अनन्य है)।

if (item[testpos] > goal) 
{ 
    // new best-so-far 
    upperbound = testpos; 
} 
else 
{ 
    lowerbound = testpos + 1; 
} 

जब लोअर और अपर सीमा के बीच की श्रेणी में खाली है (आधे खुले उपयोग करते हुए, जब दोनों एक ही सूचकांक है), अपने परिणाम है आपका सबसे हाल का सबसे तो दूर समाधान, बस ऊपर अपने ऊपरी बाउंड (यानी आधे खुले के लिए ऊपरी बाउंड इंडेक्स पर)।

तो पूर्ण एल्गोरिथ्म ... है

while (upperbound > lowerbound) 
{ 
    testpos = lowerbound + ((upperbound-lowerbound)/2); 

    if (item[testpos] > goal) 
    { 
    // new best-so-far 
    upperbound = testpos; 
    } 
    else 
    { 
    lowerbound = testpos + 1; 
    } 
} 

first key > goal से first key >= goal को बदलने के लिए आपको सचमुच if लाइन में तुलना ऑपरेटर स्विच करें। रिश्तेदार ऑपरेटर और लक्ष्य को एक पैरामीटर द्वारा प्रतिस्थापित किया जा सकता है - एक अनुमानित फ़ंक्शन जो सत्य लौटाता है (और केवल अगर) इसका पैरामीटर लक्ष्य के किनारे से अधिक है।

जो आपको "पहला>" और "पहला> =" देता है। "पहले ==" प्राप्त करने के लिए, "first> =" और का उपयोग लूप निकालने के बाद समानता जांच जोड़ें।

"अंतिम <" आदि के लिए, सिद्धांत उपरोक्त जैसा ही है, लेकिन सीमा परिलक्षित होती है। इसका मतलब है कि आप बाध्य समायोजन (लेकिन टिप्पणी नहीं) के साथ-साथ ऑपरेटर को बदलना भी बदलते हैं। लेकिन ऐसा करने से पहले, निम्नलिखित पर विचार करें ...

a > b == !(a <= b) 
a >= b == !(a < b) 

भी ...

• स्थिति (पिछले कुंजी < लक्ष्य) = स्थिति (पहली कुंजी> = लक्ष्य) - 1
• स्थिति (पिछले कुंजी < = लक्ष्य) = स्थिति (पहली कुंजी> लक्ष्य) - 1

जब हम खोज के दौरान अपनी सीमाओं को स्थानांतरित करते हैं, तब तक दोनों पक्ष लक्ष्य तक पहुंचने तक लक्ष्य की ओर बढ़ रहे हैं। और वहाँ सिर्फ लोअर बाउंड नीचे एक विशेष आइटम है, वहाँ सिर्फ ऊपरी सीमा से ऊपर है बस के रूप में ...

while (upperbound > lowerbound) 
{ 
    testpos = lowerbound + ((upperbound-lowerbound)/2); 

    if (item[testpos] > goal) 
    { 
    // new best-so-far for first key > goal at [upperbound] 
    upperbound = testpos; 
    } 
    else 
    { 
    // new best-so-far for last key <= goal at [lowerbound - 1] 
    lowerbound = testpos + 1; 
    } 
} 

तो एक तरह से, हम दो पूरक एक ही बार में चल रहे खोज नहीं हैं। जब ऊपरी और निचले स्तर की बैठक होती है, तो हमारे पास उस एकल सीमा के प्रत्येक तरफ एक उपयोगी खोज परिणाम होता है।

सभी मामलों के लिए, मौका है कि एक मूल "काल्पनिक" सीमा से बाहर सर्वोत्तम-दूर की स्थिति आपका अंतिम परिणाम था ( खोज सीमा में कोई मिलान नहीं था)। अंतिम == करने से पहले इसे पहले == और अंतिम == मामलों की जांच करने से पहले जांचना होगा। यह उपयोगी व्यवहार भी हो सकता है - उदा। यदि आप अपने लक्ष्य आइटम को सम्मिलित करने की स्थिति खोज रहे हैं, तो अपने मौजूदा आइटमों के अंत के बाद इसे जोड़ना सही बात है यदि सभी मौजूदा आइटम आपके लक्ष्य आइटम से छोटे हैं।

testpos के चयन पर कुछ नोट ...

testpos = lowerbound + ((upperbound-lowerbound)/2); 

सबसे पहले, यह होगा कभी नहीं अतिप्रवाह, और अधिक स्पष्ट ((lowerbound + upperbound)/2) के विपरीत है। यह पॉइंटर्स के साथ-साथ पूर्णांक अनुक्रमणिका के साथ भी काम करता है।

दूसरा, विभाजन को गोल करने के लिए माना जाता है। गैर-नकारात्मक के लिए गोल करना ठीक है (आप सभी सी में सुनिश्चित हो सकते हैं) क्योंकि अंतर हमेशा गैर-नकारात्मक है।

यह एक पहलू है जिसे आप देखभाल की आवश्यकता हो सकती है यदि आप अर्ध-खुले श्रेणियों का उपयोग करते हैं, हालांकि - सुनिश्चित करें कि परीक्षण स्थिति खोज सीमा के अंदर है, न केवल बाहर (पहले से ही पाए गए सर्वश्रेष्ठ- बहुत दूर की स्थिति)।

अंत में, एक द्विआधारी पेड़ तलाश में, सीमा से आगे बढ़ निहित है और testpos की पसंद पेड़ की संरचना (जो असंतुलित हो सकता है) में बनाया गया है, फिर भी इसी सिद्धांत क्या खोज है के लिए आवेदन करते हुए। इस मामले में, हम अंतर्निहित श्रेणियों को कम करने के लिए हमारे बच्चे नोड का चयन करते हैं। पहले मैच मामलों के लिए, या तो हमें एक नया छोटा सर्वश्रेष्ठ मैच मिला है (एक छोटे से छोटे और बेहतर को खोजने की उम्मीद में निचले बच्चे के पास जाएं) या हमने ओवरशॉट किया है (पुनर्प्राप्त होने की उम्मीद में उच्च बच्चे को जाएं)। फिर, तुलनात्मक ऑपरेटर को स्विच करके चार मुख्य मामलों को संभाला जा सकता है।

बीटीडब्ल्यू - उस टेम्पलेट पैरामीटर के लिए उपयोग करने के लिए अधिक संभावित ऑपरेटर हैं। साल के आधार पर क्रमबद्ध एक सरणी पर विचार करें। शायद आप किसी विशेष वर्ष के लिए पहला आइटम खोजना चाहते हैं। ऐसा करने के लिए, तुलनात्मक कार्य लिखें जो वर्ष की तुलना करता है और महीने को अनदेखा करता है - लक्ष्य बराबर की तुलना करता है यदि वर्ष बराबर है, लेकिन लक्ष्य मान कुंजी के लिए एक अलग प्रकार हो सकता है जिसमें एक महीने का मूल्य भी नहीं है की तुलना करें। मैं इसे "आंशिक कुंजी तुलना" के रूप में सोचता हूं, और अपने बाइनरी खोज टेम्पलेट में प्लग करता हूं और आपको "आंशिक कुंजी खोज" के रूप में लगता है।

EDIT नीचे दिया गया पैराग्राफ "31 दिसंबर 1 999 को 1 फरवरी 2000 के बराबर" कहता था। यह तब तक काम नहीं करेगा जब तक कि बीच में पूरी सीमा को बराबर नहीं माना जाता। मुद्दा यह है कि शुरुआत के सभी तीन हिस्सों और अंतराल की तिथियां अलग-अलग हैं, इसलिए आप "आंशिक" कुंजी से निपट नहीं रहे हैं, लेकिन खोज के बराबर मानी जाने वाली कुंजियों को कंटेनर में एक संगत ब्लॉक बनाना चाहिए, जो आमतौर पर संभावित कुंजी के क्रमबद्ध सेट में एक संगत ब्लॉक को इंगित करेगा।

यह कड़ाई से सिर्फ "आंशिक" कुंजी नहीं है, या तो। आपकी कस्टम तुलना 31 दिसंबर 1 999 को 1 जनवरी 2000 के बराबर होने पर विचार कर सकती है, फिर भी अन्य सभी तिथियां अलग-अलग हैं। बिंदु यह है कि कस्टम तुलना ऑर्डरिंग के मूल मूल के साथ सहमत होनी चाहिए, लेकिन यह सभी अलग-अलग मानों पर विचार करने के बारे में इतना पसंद नहीं हो सकता है - यह "समकक्ष वर्ग" के रूप में कई प्रकार की चाबियों का इलाज कर सकता है।

---

सीमा है कि मैं वास्तव में पहले शामिल किया जाना चाहिए था के बारे में एक अतिरिक्त ध्यान दें, लेकिन मैं समय पर इस तरह से इसके बारे में सोचा नहीं था।

सीमाओं के बारे में सोचने का एक तरीका यह है कि वे आइटम अनुक्रमणिका नहीं हैं। एक बाध्य दो आइटम के बीच की सीमा रेखा

|  |  |  |  |  |  |  |  | 
| +-+ | +-+ | +-+ | +-+ | +-+ | +-+ | +-+ | +-+ | 
| |0| | |1| | |2| | |3| | |4| | |5| | |6| | |7| | 
| +-+ | +-+ | +-+ | +-+ | +-+ | +-+ | +-+ | +-+ | 
|  |  |  |  |  |  |  |  | 
0  1  2  3  4  5  6  7  8 

जाहिर सीमा से नंबरिंग मदों की नंबरिंग से संबंधित है, तो आप के रूप में आसानी सीमा रेखा नंबर कर सकते हैं के रूप में आप आइटम नंबर कर सकते हैं ...। जब तक आप अपनी सीमाओं को बाएं से दाएं तक सीमित करते हैं और वैसे ही आप अपनी वस्तुओं को संख्या देते हैं (इस मामले में शून्य से शुरू होता है) परिणाम आम तौर पर आम आधे खुले सम्मेलन के समान होता है।

रेंज को दो में सटीक रूप से विभाजित करने के लिए एक मध्य बाध्य का चयन करना संभव होगा, लेकिन यह एक बाइनरी खोज नहीं है। बाइनरी खोज के लिए, आप परीक्षण करने के लिए एक आइटम का चयन करें - बाध्य नहीं। उस आइटम का पुनरावृत्ति इस परीक्षण में किया जाएगा और फिर कभी परीक्षण नहीं किया जाना चाहिए, इसलिए इसे दोनों subranges से बाहर रखा गया है।

|  |  |  |  |  |  |  |  | 
| +-+ | +-+ | +-+ | +-+ | +-+ | +-+ | +-+ | +-+ | 
| |0| | |1| | |2| | |3| | |4| | |5| | |6| | |7| | 
| +-+ | +-+ | +-+ | +-+ | +-+ | +-+ | +-+ | +-+ | 
|  |  |  |  |  |  |  |  | 
0  1  2  3  4  5  6  7  8 
         ^
     |<-------------------|------------->| 
          | 
     |<--------------->| | |<--------->| 
      low range  i  hi range 

तो testpos और testpos+1 एल्गोरिथ्म में बाध्य सूचकांक में आइटम सूचकांक अनुवाद के दो मामले हैं। बेशक यदि दो सीमाएं बराबर हैं, तो उस सीमा में कोई भी आइटम नहीं है ताकि लूप जारी नहीं रह सके, और एकमात्र संभावित परिणाम यह है कि एक बाध्य मूल्य है।

ऊपर दिखाए गए श्रेणियां केवल अभी तक की जाने वाली श्रेणियां हैं - जो अंतर हम सिद्ध-निचले और सिद्ध उच्च श्रेणी के बीच बंद करना चाहते हैं।

इस मॉडल में, बाइनरी खोज दो आदेशित प्रकार के मूल्यों के बीच सीमा की खोज कर रही है - जिन्हें "निचला" और "उच्च" के रूप में वर्गीकृत किया गया है। भविष्यवाणी परीक्षण एक आइटम वर्गीकृत करता है। कोई "बराबर" वर्ग नहीं है - बराबर-से-कुंजी मान उच्च वर्ग (x[i] >= key के लिए) या निम्न वर्ग (x[i] > key के लिए) का हिस्सा हैं।