आज कुछ कोड लिखने में, मैंने एक परिस्थिति पर ऐसा किया है जिसने मुझे एक तरह की बाइनरी खोज लिखने के लिए प्रेरित किया है जिसे मैंने कभी नहीं देखा है। क्या इस बाइनरी खोज का नाम है, और क्या यह वास्तव में एक "बाइनरी" खोज है?क्या इस प्रकार की बाइनरी खोज के लिए कोई नाम है?
प्रेरणा
सबसे पहले, क्रम खोज को समझने के लिए आसान बनाने के लिए, मैं उपयोग के मामले कि इसके निर्माण के पैदा की व्याख्या करेगा।
कहें कि आपके पास आदेशित संख्याओं की एक सूची है। आपको उस सूची में संख्या का सूचकांक ढूंढने के लिए कहा जाता है जो x के सबसे नज़दीक है।
int findIndexClosestTo(int x);
कॉल करने के लिए findIndexClosestTo()हमेशा इस नियम का पालन करें:
तो
findIndexClosestTo()के अंतिम परिणामiथा, तोiके करीब के लिए वर्तमान कॉल का परिणाम होने का अधिक से अधिक संभावना सूचकांक होते हैंfindIndexClosestTo()।
दूसरे शब्दों में, इस सूचकांक को हमें इस समय खोजने की आवश्यकता है जो हमने उससे आगे की तुलना में आखिरी बार के करीब होने की संभावना है।
उदाहरण के लिए, एक अनुरूपित लड़का की कल्पना करें जो स्क्रीन पर बाएं और दाएं चलती है। अगर हम अक्सर लड़के के स्थान की अनुक्रमणिका से पूछताछ कर रहे हैं, तो संभवतः वह उस अंतिम स्थान के पास कहीं है जहां हमने उसे पाया था।
एल्गोरिथ्म
उपरोक्त मामले को देखते हुए, हम जानते हैं कि findIndexClosestTo() के अंतिम परिणाम i था (यदि यह वास्तव में पहली बार समारोह बुलाया गया है है, सूची के बीच सूचकांक, सादगी के लिए करने के लिए i चूक, हालांकि पहली कॉल के परिणाम को खोजने के लिए एक अलग बाइनरी खोज वास्तव में तेज होगी), और फ़ंक्शन को फिर से बुलाया गया है। नया नंबर x देखते हुए, हम अपने सूचकांक खोजने के लिए इस एल्गोरिथ्म का पालन करें:
interval = 1;- संख्या हम के लिए,
xदेख रहे हैं,iपर तैनात है? यदि ऐसा है, तोiलौटाएं; - यदि नहीं, तो निर्धारित करें कि
xiसे ऊपर या नीचे है या नहीं। (याद रखें, सूची क्रमबद्ध है।) - की दिशा में
intervalसूचकांक ले जाएं। - यदि हमें हमारे नए स्थान पर
xमिल गया है, तो उस स्थान को वापस करें। - डबल
interval। (यानीinterval *= 2) - हम
xबीत चुके हैं, वापसintervalसूचकांक जाना,interval = 1निर्धारित करते हैं, 4.
संभावना नियम (प्रेरणा शीर्षक के अंतर्गत) ऊपर कहा गया है को देखते हुए जाने के लिए, यह होने के लिए मुझे ऐसा लगता है सही सूचकांक खोजने का सबसे प्रभावी तरीका। क्या आप तेजी से जानते हैं?
मुझे लगता है कि यह वास्तव में एक सरणी है और सूची नहीं है? क्योंकि सूची में बाइनरी खोज बेवकूफ होगी। – Nemo
मुझे लगता है कि सबसे अच्छा जवाब इस बात पर निर्भर करेगा कि i पर आधारित स्थिति के लिए संभाव्यता वितरण क्या है। उदाहरण के लिए यदि 99% मौका है जो कि 3 में से एक है तो एक बहुत ही अलग उत्तर उपयोगी होगा यदि यह कहीं भी 0.001% अधिक होने की संभावना है। मुझे लगता है कि इष्टतम उत्तर एक संभाव्यता आधारित वितरण होगा जैसे बाइनरी खोज एक ऐसी जगह चुनती है जो प्रत्येक तरफ वांछित वस्तु का 50% मौका देती है। तो यदि आप संभाव्यता वक्र को परिभाषित कर सकते हैं तो आप शायद एक सुंदर अच्छा एल्गोरिदम परिभाषित कर सकते हैं। – Chris
@Chris बहुत अच्छा बिंदु। यदि सभी डेटा बिंदु _nearly_ संभावना में बराबर थे, तो यह नियमित बाइनरी खोज से भी बदतर होगा। मेरे मामले में, संभावना है कि आप आखिरी बिंदु से आगे बढ़ने के बाद तेजी से क्षय हो जाते हैं, इस मामले में, मेरा मानना है कि यह खोज तेज़ है। –