डेटा स्ट्रक्चर पर फिंगर सर्च (Finger Search) को किसी भी खोज ऑपरेशन के विस्तार के रूप में परिभाषित किया जाता है जिसे वह स्ट्रक्चर समर्थन करता है, जहां डेटा स्ट्रक्चर में एक एलिमेंट का संदर्भ (फिंगर) क्वेरी के साथ दिया जाता है। जबकि किसी एलिमेंट के लिए खोज समय को अक्सर डेटा स्ट्रक्चर में एलिमेंट्स की संख्या के फंक्शन के रूप में दर्शाया जाता है, फिंगर खोज समय को एलिमेंट और फिंगर के बीच की दूरी के फंक्शन के रूप में माना जाता है।
m एलिमेंट्स के एक सेट में, दो एलिमेंट्स a और b के बीच की दूरी d(a, b) उनके रैंक में अंतर है। यदि एलिमेंट्स a और b संरचना में i-वें और j-वें सबसे बड़े एलिमेंट्स हैं, तो रैंक में अंतर |i - j| है। यदि किसी संरचना में सामान्य खोज में सामान्यतः O(f(m)) समय लगता है, तो फिंगर एलिमेंट b के साथ एलिमेंट a के लिए फिंगर खोज को आदर्श रूप से O(f(d)) समय लेना चाहिए। ध्यान दें कि चूंकि d ≤ m, यह निम्नलिखित है कि सबसे खराब स्थिति में, फिंगर खोज केवल सामान्य खोज जितनी खराब है। हालांकि, व्यवहार में ये पतनशील फिंगर खोज सामान्य खोज से अधिक काम करती हैं। उदाहरण के लिए, यदि f(n) log(n) है, और फिंगर खोज सबसे खराब स्थिति में सामान्य खोज से दोगुनी तुलना करती है, तो यह निम्नलिखित है कि फिंगर खोज धीमी है जब d > √n। इसलिए, फिंगर खोज केवल तभी लागू की जानी चाहिए जब कोई उचित रूप से उम्मीद कर सके कि लक्ष्य वास्तव में फिंगर के करीब है।
कार्यान्वयन (Implementations)
कुछ लोकप्रिय डेटा स्ट्रक्चर वास्तविक संरचना में अतिरिक्त परिवर्तन के बिना फिंगर खोज का समर्थन करते हैं। जिन संरचनाओं में एलिमेंट a की खोज एक अंतराल को संकीर्ण करके की जाती है जिस पर a पाया जा सकता है, वहां एलिमेंट b से फिंगर खोज आमतौर पर b से खोज प्रक्रिया को उलट कर की जाती है जब तक कि खोज अंतराल a को समाहित करने के लिए पर्याप्त बड़ा न हो जाए, उस बिंदु पर खोज सामान्य रूप से आगे बढ़ती है।
सॉर्टेड लिंक्ड लिस्ट्स (Sorted Linked Lists)
लिंक्ड लिस्ट में, कोई सामान्यतः एक छोर से दूसरे छोर तक पार करके एलिमेंट के लिए रैखिक तरीके से खोज करता है। यदि लिंक्ड लिस्ट सॉर्टेड है, और हमारे पास एलिमेंट b वाले नोड का संदर्भ है, तो हम एलिमेंट a को O(d) समय में b से शुरू करके खोज सकते हैं।
सॉर्टेड एरे (Sorted Arrays)
सॉर्टेड एरे B में, कोई सामान्यतः बाइनरी सर्च (Binary Search) द्वारा एलिमेंट a को B में खोजता है। फिंगर खोज B[j] = b से वन-साइडेड सर्च (One-sided Search) लागू करके की जाती है। जहां बाइनरी सर्च प्रत्येक तुलना के बाद खोज स्थान को आधा कर देता है, वन-साइडेड सर्च प्रत्येक तुलना के बाद खोज स्थान को दोगुना कर देता है। विशेष रूप से, वन-साइडेड खोज के k-वें पुनरावृत्ति पर (मान लें 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) समय लेती है।
स्किप लिस्ट्स (Skip Lists)
स्किप लिस्ट में, कोई एलिमेंट a के लिए नोड से जिसमें एलिमेंट b है, फिंगर सर्च कर सकता है बस इस बिंदु से खोज जारी रखकर। ध्यान दें कि यदि a < b, तो खोज पिछड़े दिशा में आगे बढ़ती है, और यदि a > b, तो खोज आगे की दिशा में आगे बढ़ती है। पिछड़ा हुआ केस स्किप लिस्ट में सामान्य खोज के सममित है, लेकिन आगे का केस वास्तव में अधिक जटिल है। आम तौर पर, स्किप लिस्ट में खोज तेज होने की उम्मीद है क्योंकि सूची की शुरुआत में सेंटिनल को सबसे लंबा नोड माना जाता है। हालांकि, हमारी फिंगर ऊंचाई 1 के नोड हो सकती है। इसके कारण, हम खोज करने की कोशिश करते हुए शायद ही कभी चढ़ते हैं; ऐसा कुछ जो सामान्य रूप से कभी नहीं होता। हालांकि, इस जटिलता के साथ भी, हम O(log d) अपेक्षित खोज समय प्राप्त कर सकते हैं।
ट्रेप्स (Treaps)
ट्रेप को एक रैंडमाइज़्ड बाइनरी सर्च ट्री (Randomized Binary Search Tree - BST) के रूप में परिभाषित किया जाता है। ट्रेप में खोज किसी अन्य BST में एलिमेंट खोजने के समान है। ट्रेप्स में हालांकि यह गुण होता है कि दूरी d के दो एलिमेंट्स के बीच अपेक्षित पथ लंबाई O(log d) होती है। इस प्रकार, एलिमेंट b वाले नोड से एलिमेंट a के लिए फिंगर सर्च करने के लिए, कोई b एलिमेंट से ट्री पर तब तक चढ़ सकता है जब तक एलिमेंट a का पूर्वज न मिल जाए, जिस बिंदु पर सामान्य BST खोज सामान्य तरीके से आगे बढ़ती है। जबकि यह गणना करना कि क्या एक नोड दूसरे का पूर्वज है, गैर-तुच्छ है, कोई ट्री को इस रूप के क्वेरी का समर्थन करने के लिए बढ़ा सकता है ताकि अपेक्षित O(log d) फिंगर सर्च समय प्रदान किया जा सके।
रोप्स और ट्रीज़ (Ropes and Trees)
रोप (Rope) डेटा स्ट्रक्चर के कार्यान्वयन आमतौर पर स्ट्रिंग को विज़िट करने के लिए कॉर्ड पोजीशन इटरेटर (Cord Position Iterator) का उपयोग करते हैं। इटरेटर को एक फिंगर माना जा सकता है जो स्ट्रिंग के किसी विशिष्ट वर्ण पर इंगित करता है। अधिकांश संतुलित ट्रीज़ की तरह, रोप्स को केवल ट्री के रूट दिए जाने पर ट्री के एक लीफ में डेटा पुनः प्राप्त करने के लिए O(log m) समय की आवश्यकता होती है। ट्री के हर लीफ को पढ़ने के लिए O(m log m) समय की आवश्यकता प्रतीत होगी। हालांकि, थोड़ी अतिरिक्त जानकारी संग्रहीत करके, इटरेटर को "अगला" लीफ केवल O(1) समय में पढ़ने के लिए लागू किया जा सकता है, और ट्री के हर लीफ को केवल O(m) समय में।
