क्या सुनहरी अनुभाग खोज बाइनरी खोज से बेहतर है?

Question

हाल ही में मैंने एक राय सुना है कि बाइनरी खोज को 2 के बजाय फाई (सुनहरा राशन) द्वारा विभाजित करके ले जाया जा सकता है। यह मेरे लिए एक बड़ा आश्चर्य था, क्योंकि मैंने कभी इस तरह के अनुकूलन के बारे में नहीं सुना है। क्या ये सच है? क्या यह सच होगा यदि विभाजन 2 और फाई द्वारा समान रूप से प्रदर्शन किया गया था?

यदि नहीं, तो क्या कोई सामान्य परिस्थितियां हैं जिसके अंतर्गत सुनहरी अनुभाग खोज द्विआधारी खोज से तेज़ी से प्रदर्शन करेगी?

यूपीडी: एक गैर-प्रासंगिक विकिपीडिया आलेख को लिंक हटाने के लिए संपादित किया गया। भ्रामक के लिए खेद है।

Answer 1

"फिबोनाकी खोज" नामक दो एल्गोरिदम हैं।

The article you linked अधिकतम या न्यूनतम कार्यों को खोजने के लिए संख्यात्मक एल्गोरिदम के बारे में है। यह इस समस्या के लिए इष्टतम एल्गोरिदम है। यह समस्या बाइनरी खोज समस्या से काफी अलग है कि यह उचित किसी भी दिए गए मामले के लिए स्पष्ट होना चाहिए।

The other kind of Fibonacci search द्विआधारी खोज के समान समस्या पर हमला करता है। बाइनरी खोज अनिवार्य रूप से हमेशा बेहतर है। Knuth लिखते हैं कि Fibonacci खोज "कुछ कंप्यूटरों पर बेहतर है, क्योंकि इसमें केवल जोड़ और घटाव शामिल है, 2 से विभाजन नहीं।" लेकिन लगभग सभी कंप्यूटर बाइनरी अंकगणित का उपयोग करते हैं, जिसमें 2 से विभाजन सरल अतिरिक्त और घटाव से अधिक है।

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

Answer 2

"तेजी से काम करता है" अस्पष्ट है; लेकिन बाइनरी खोज में पहुंच की संख्या के लिए सबसे कम सबसे खराब मामला होना चाहिए।

Answer 3

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