घातीय खोज

घातीय खोज

Class	Search algorithm
Data structure	Array
Worst-case performance	O(log i)
Best-case performance	O(1)
Average performance	O(log i)
Worst-case space complexity	O(1)

कंप्यूटर विज्ञान में, एक घातीय खोज (जिसे दोहरीकरण खोज या सरपट खोज या स्ट्रुज़िक खोज भी कहा जाता है)एक कलन विधि है, जो जॉन बेंटले (कंप्यूटर वैज्ञानिक) और एंड्रयू ची-चिह याओ द्वारा 1976 में क्रमबद्ध, असीमित/अनंत सूचियों की खोज के लिए बनाया गया था।इसे लागू करने के कई तरीके हैं, जिनमें से सबसे आम है उस सीमा को निर्धारित करना जिसमें खोज कुंजी स्थित है और उस सीमा के भीतर एक बाइनरी खोज करना है। यह बिग-ओ नोटेशन (लॉग i) लेता है जहां i सूची में खोज कुंजी की स्थिति है, यदि खोज कुंजी सूची में है, या वह स्थिति जहां खोज कुंजी होनी चाहिए, यदि खोज कुंजी सूची में नहीं है सूची।

घातीय खोज का उपयोग बंधी हुई सूचियों में खोजने के लिए भी किया जा सकता है। घातीय खोज बाउंडेड सूचियों के लिए अधिक पारंपरिक खोजों से भी बेहतर प्रदर्शन कर सकती है, जैसे कि बाइनरी खोज, जब खोजा जा रहा तत्व सरणी की शुरुआत के करीब होता है। ऐसा इसलिए है क्योंकि घातीय खोज O(log i) समय में चलेगी, जहां i सूची में खोजे जा रहे तत्व का सूचकांक है, जबकि बाइनरी खोज O(log n) समय में चलेगी, जहां n तत्वों की संख्या है सूची में।

एल्गोरिथम

घातीय खोज एक निर्दिष्ट इनपुट मान (खोज कुंजी) के लिए क्रमबद्ध, असीमित सूची के माध्यम से खोज करने की अनुमति देती है। एल्गोरिदम में दो चरण होते हैं. पहला चरण एक सीमा निर्धारित करता है जिसमें खोज कुंजी सूची में होने पर स्थित होगी। दूसरे चरण में, इस श्रेणी पर एक बाइनरी खोज की जाती है। पहले चरण में, यह मानते हुए कि सूची को आरोही क्रम में क्रमबद्ध किया गया है, एल्गोरिदम पहले घातांक, जे की तलाश करता है, जहां मान 2 है^j खोज कुंजी से बड़ा है. यह मान, 2^j 2, 2 की पिछली शक्ति के साथ बाइनरी खोज के लिए ऊपरी सीमा बन जाता है^{j - 1}, बाइनरी खोज के लिए निचली सीमा है।

// Returns the position of key in the array arr of length size.
template <typename T>
int exponential_search(T arr[], int size, T key)
{
    if (size == 0) {
        return NOT_FOUND;
    }

    int bound = 1;
    while (bound < size && arr[bound] < key) {
        bound *= 2;
    }

    return binary_search(arr, key, bound/2, min(bound + 1, size));
}

प्रत्येक चरण में, एल्गोरिदम वर्तमान खोज सूचकांक में खोज कुंजी मान की तुलना कुंजी मान से करता है। यदि वर्तमान सूचकांक पर तत्व खोज कुंजी से छोटा है, तो एल्गोरिदम दोहराता है, इसे दोगुना करके अगले खोज सूचकांक पर जाता है, 2 की अगली शक्ति की गणना करता है।यदि वर्तमान सूचकांक में तत्व खोज कुंजी से बड़ा है, तो एल्गोरिदम अब जानता है कि खोज कुंजी, यदि यह सूची में बिल्कुल भी शामिल है, तो पिछले खोज सूचकांक द्वारा गठित अंतराल में स्थित है, 2^{j - 1}, और वर्तमान खोज सूचकांक, 2^j. यदि खोज कुंजी सूची में नहीं है, या सूची में खोज कुंजी की स्थिति है, तो बाइनरी खोज या तो किसी विफलता के परिणाम के साथ की जाती है।

प्रदर्शन

एल्गोरिदम के पहले चरण में O(लॉग i) समय लगता है, जहां i वह सूचकांक है जहां सूची में खोज कुंजी होगी। ऐसा इसलिए है, क्योंकि बाइनरी खोज के लिए ऊपरी सीमा निर्धारित करने में, जबकि लूप बिल्कुल निष्पादित होता है $\lceil \log(i)\rceil$ बार. चूंकि सूची को खोज सूचकांक को दोगुना करने के बाद क्रमबद्ध किया गया है $\lceil \log(i)\rceil$ कई बार, एल्गोरिथ्म एक खोज सूचकांक पर होगा जो कि i से अधिक या उसके बराबर है $2^{\lceil \log(i)\rceil }\geq i$. इस प्रकार, एल्गोरिथम के पहले चरण में O(log i) समय लगता है।

एल्गोरिथम का दूसरा भाग भी O(log i) समय लेता है। चूंकि दूसरा चरण केवल एक द्विआधारी खोज है, इसमें O(लॉग एन) लिया जाता है जहां n खोजे जा रहे अंतराल का आकार है। इस अंतराल का आकार 2 होगा^j - 2^{j - 1} जहां, जैसा कि ऊपर देखा गया है, j = log i। इसका मतलब है कि खोजे जा रहे अंतराल का आकार 2 है^{log i} - 2^{log i - 1} = 2^{log i - 1}. इससे हमें लॉग का रन टाइम मिलता है (2^{log i - 1}) = लॉग (i) - 1 = O(लॉग i).

यह एल्गोरिथम को कुल रनटाइम देता है, जिसकी गणना O(log i) + O(log i) = 2 O(log i) = O(log i) के दो चरणों के रनटाइम को जोड़कर की जाती है।

विकल्प

बेंटले और याओ ने घातीय खोज के लिए कई विविधताएँ सुझाईं।एल्गोरिथम के दूसरे चरण में बाइनरी खोज के लिए ऊपरी सीमा का निर्धारण करते समय, इन विविधताओं में एक यूनरी खोज के विपरीत, एक बाइनरी खोज करना शामिल होता है। यह एल्गोरिथम के पहले चरण को दो भागों में विभाजित करता है, जिससे एल्गोरिथम कुल मिलाकर तीन-चरण वाला एल्गोरिथम बन जाता है। नया पहला चरण एक मान निर्धारित करता है$j'$, बहुत कुछ पहले जैसा, वैसा $2^{j'}$ खोज कुंजी से बड़ा है और $2^{j'/2}$ खोज कुंजी से कम है. पहले,$j'$2 की अगली घात की गणना करके (अर्थात, j में 1 जोड़कर) एकात्मक तरीके से निर्धारित किया गया था। प्रकारांतर में यह प्रस्तावित है कि $j'$ इसके बजाय दोगुना कर दिया गया है (उदाहरण के लिए, 2 से कूदकर)।² से 2⁴ 2 के विपरीत³). पहला$j'$ऐसा है कि $2^{j'}$ खोज कुंजी से अधिक होने पर यह पहले की तुलना में अधिक कठोर ऊपरी सीमा बनाती है। एक बार यह$j'$पाया जाता है, एल्गोरिथ्म अपने दूसरे चरण में चला जाता है और द्वारा गठित अंतराल पर एक बाइनरी खोज की जाती है $j'/2$ और $j'$, अधिक सटीक ऊपरी सीमा घातांक जे दे रहा है। यहां से, एल्गोरिदम का तीसरा चरण अंतराल 2 पर बाइनरी खोज करता है^{j - 1} और 2^j, पहले जैसा। इस विविधता का प्रदर्शन है $\lfloor \log i\rfloor +2\lfloor \log(\lfloor \log i\rfloor +1)\rfloor +1$ = O(लॉग i).

बेंटले और याओ इस भिन्नता को सामान्यीकृत करते हैं जहां एल्गोरिथ्म के पहले चरण के दौरान बाइनरी खोजों की कोई भी संख्या, k, निष्पादित की जाती है, जिससे k-नेस्टेड बाइनरी खोज भिन्नता मिलती है। मूल घातीय खोज एल्गोरिदम की तरह, ओ (लॉग i) समय में चलने वाली विविधताओं के लिए एसिम्प्टोटिक रनटाइम नहीं बदलता है।

इसके अलावा, जब के-नेस्टेड बाइनरी खोज के उपरोक्त परिणाम का उपयोग क्रमबद्ध सरणी पर किया जाता है, तो बिखरा हुआ पेड़ के एक तंग संस्करण के साथ एक डेटा संरचना दी जा सकती है।इसका उपयोग करते हुए, खोज के दौरान की गई तुलनाओं की संख्या लॉग (डी) + लॉग लॉग (डी) + ... + ओ (लॉग) है^*d), जहां d एक्सेस किए गए अंतिम तत्व और एक्सेस किए जा रहे वर्तमान तत्व के बीच रैंक का अंतर है।

अनुप्रयोग

खोज बैंड को तेजी से बढ़ाने पर आधारित एक एल्गोरिदम O(ns) के लिए अनुक्रम संरेखण को हल करता है, जहां n अनुक्रमों की लंबाई है और s उनके बीच की संपादन दूरी है।

यह भी देखें

• रेखीय खोज
• द्विआधारी खोज
• अंतर्वेशन खोज
• टर्नरी खोज
• हैश तालिका