डेटा संरचना पर एक उंगली खोज को किसी भी खोज ऑपरेशन के विस्तार के रूप में परिभाषित किया जाता है जो संरचना का समर्थन करता है, जहां डेटा संरचना में एक तत्व के लिए एक संदर्भ (उंगली) क्वेरी के साथ दिया जाता है। जबकि किसी तत्व के लिए खोज समय को अक्सर डेटा संरचना में तत्वों की संख्या के एक कार्य के रूप में दर्शाया जाता है, उंगली खोज समय को तत्व और उंगली के बीच की दूरी के कार्य के रूप में माना जाता है।
एम तत्वों के एक सेट में, दूरी डी (ए, बी) दो तत्वों ए और बी के बीच रैंक में उनका अंतर है। यदि तत्व a और b संरचना में i-th और j-th सबसे बड़े तत्व हैं, तो रैंक में अंतर है |i - j|। यदि किसी संरचना में सामान्य खोज सामान्य रूप से ओ (एफ (एम)) समय का उपभोग करती है, तो तत्व ए के लिए उंगली तत्व बी के लिए एक उंगली खोज आदर्श रूप से ओ (एफ (डी)) समय का उपभोग करना चाहिए। टिप्पणी करें कि d m के बाद से, यह इस प्रकार है कि सबसे खराब स्थिति में, उंगली की खोज सामान्य खोज जितनी ही खराब है। हालाँकि, व्यवहार में ये पतित उंगली खोजें सामान्य खोजों की तुलना में अधिक कार्य करती हैं। उदाहरण के लिए, यदि f(n) लॉग (n) है, और सबसे खराब स्थिति में उंगली की खोज सामान्य खोज की तुलना में दोगुनी तुलना करती है, तो यह इस प्रकार है कि d> n होने पर उंगली की खोज धीमी होती है। इसलिए, उंगली की खोज केवल तभी लागू की जानी चाहिए जब कोई उचित रूप से उम्मीद कर सकता है कि लक्ष्य वास्तव में उंगली के करीब होगा।
कार्यान्वयन
कुछ लोकप्रिय डेटा संरचनाएं वास्तविक संरचना में अतिरिक्त परिवर्तन किए बिना उंगलियों की खोज का समर्थन करती हैं। संरचनाओं में जहां एक तत्व की खोज एक अंतराल को कम करके की जाती है, जिस पर एक पाया जा सकता है, तत्व बी से उंगली की खोज आम तौर पर बी से खोज प्रक्रिया को उलट कर की जाती है जब तक कि खोज अंतराल तत्व ए को शामिल करने के लिए पर्याप्त बड़ा न हो, पर किस बिंदु पर खोज सामान्य रूप से आगे बढ़ती है।
सॉर्ट की गई लिंक की गई सूचियां
एक लिंक्ड सूची में, एक आम तौर पर एक छोर से दूसरे छोर तक एक तत्व के लिए रैखिक तरीके से खोज करता है। यदि लिंक की गई सूची को सॉर्ट किया गया है, और हमारे पास तत्व बी वाले कुछ नोड का संदर्भ है, तो हम तत्व बी से अपनी खोज शुरू करके ओ (डी) समय में तत्व ढूंढ सकते हैं।
क्रमबद्ध सरणियाँ
एक क्रमबद्ध सरणी बी में, एक सामान्य रूप से एक बाइनरी खोज के साथ बी में एक तत्व की खोज करता है। उंगलियों की खोज B[j] =b से एकतरफा खोज को लागू करके की जाती है। जबकि द्विआधारी खोज प्रत्येक तुलना के बाद खोज स्थान को आधा कर देती है, एक तरफा खोज प्रत्येक तुलना के बाद खोज स्थान को दोगुना कर देती है। विशेष रूप से, एक तरफा खोज के kth पुनरावृत्ति पर (a>b मानकर), विचाराधीन अंतराल B[j, j+2 k-1 है ]. B[j + 2 k-1 . जैसे ही विस्तार रुक जाता है ] a, जिस बिंदु पर यह अंतराल तत्व a के लिए बाइनरी सर्च किया जाता है। यदि एक तरफा खोज तत्व a वाले अंतराल को खोजने के लिए k पुनरावृत्तियों का उपभोग करती है, तो यह इस प्रकार है कि d> 2 k-2 . इस श्रेणी की खोज करने वाला बाइनरी एक और k पुनरावृत्ति का भी उपभोग करेगा। इसलिए, b से a के लिए फिंगर सर्च में O(k) =O(log d) समय लगता है
।
छोड़ें सूचियां
एक स्किप सूची में, कोई भी इस बिंदु से केवल खोज जारी रखते हुए तत्व बी युक्त नोड से तत्व की खोज कर सकता है। ध्यान दें कि यदि a
ट्रेप्स
एक ट्रैप को एक यादृच्छिक बाइनरी सर्च ट्री (BST) के रूप में परिभाषित किया गया है। ट्रैप में खोजना किसी अन्य BST में किसी तत्व की खोज करने के समान है। ट्रैप में हालांकि संपत्ति है कि दूरी के दो तत्वों के बीच अपेक्षित पथ लंबाई को ओ (लॉग डी) के रूप में दर्शाया गया है। इस प्रकार, तत्व ए के लिए तत्व बी युक्त नोड से उंगली की खोज करने के लिए, कोई भी बी तत्व से पेड़ पर चढ़ सकता है जब तक कि तत्व का पूर्वज नहीं मिल जाता है, जिस बिंदु पर सामान्य बीएसटी खोज सामान्य तरीके से आगे बढ़ती है। यह गणना करते समय कि क्या कोई नोड दूसरे का पूर्वज है, गैर-तुच्छ है, कोई अपेक्षित O(log d) उंगली खोज समय प्रदान करने के लिए इस फ़ॉर्म के प्रश्नों का समर्थन करने के लिए पेड़ को बढ़ा सकता है।
रस्सी और पेड़
रस्सी के कार्यान्वयन (डेटा संरचना) आमतौर पर स्ट्रिंग पर जाने के लिए कॉर्ड पोजीशन इटरेटर का उपयोग करते हैं। इटरेटर को एक उंगली के रूप में माना जा सकता है जो स्ट्रिंग के कुछ विशिष्ट चरित्र को इंगित करता है। अधिकांश संतुलित पेड़ों की तरह, रस्सियों को पेड़ के एक पत्ते में डेटा पुनर्प्राप्त करने के लिए ओ (लॉग (एम)) समय की आवश्यकता होती है, जब केवल पेड़ की जड़ दी जाती है। पेड़ के प्रत्येक पत्ते को पढ़ने के लिए ओ (एम * लॉग (एम)) समय की आवश्यकता होती है। हालांकि, थोड़ी अतिरिक्त जानकारी संग्रहीत करके, इटरेटर को केवल ओ (1) समय में "अगला" पत्ता पढ़ने के लिए लागू किया जा सकता है, और पेड़ के प्रत्येक पत्ते को केवल ओ (एम) समय में पढ़ा जा सकता है।