घातीय खोज

घातीय खोज

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 में क्रमबद्ध किया था, इस प्रकार से यह असीमित/अनंत सूचियों की खोज के लिए बनाया गया था। इसे प्रयुक्त करने के अनेक विधि होती हैं, जिनमें से यह सबसे समान होते है | यह उस सीमा को निर्धारित करना हैं जिसमें खोज कुंजी स्थित होती है और उस सीमा के अन्दर बाइनरी खोज करना होता है। यह O(log i) प्राप्त करता है जहां i सूची में खोज कुंजी की स्थिति है, यदि खोज कुंजी सूची में है, या वह स्थिति जहां खोज कुंजी होनी चाहिए, यदि खोज कुंजी सूची में नहीं है ।

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

एल्गोरिथम

किन्तु घातांकीय खोज निर्दिष्ट इनपुट मान (खोज कुंजी) के लिए क्रमबद्ध, असीमित सूची के माध्यम से खोज करने की अनुमति देती है। एल्गोरिदम में दो चरण प्रमुख होते हैं. प्रथम चरण सीमा निर्धारित करता है जिसमें खोज कुंजी सूची में होने पर स्थित होती है । दूसरे चरण में, इस श्रेणी पर बाइनरी खोज की जाती है। प्रथम चरण में, यह मानते हुए कि सूची को आरोही क्रम में क्रमबद्ध किया गया है, एल्गोरिदम प्रथम घातांक, j, की खोज करता है, जहां मान 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(log i) समय लगता है, जहां i वह सूचकांक है जहां सूची में खोज कुंजी होती हैं। ऐसा इसलिए है, क्योंकि बाइनरी खोज के लिए ऊपरी सीमा निर्धारित करने में, जबकि लूप बिल्कुल $\lceil \log(i)\rceil$ अनेक बार निष्पादित होता है | चूंकि सूची को खोज सूचकांक को $\lceil \log(i)\rceil$ पश्चात् दोगुना करने के क्रमबद्ध किया गया है अनेक बार, एल्गोरिथ्म खोज सूचकांक पर होता हैं जो कि $2^{\lceil \log(i)\rceil }\geq i$. से i अधिक या उसके सामान होता है इस प्रकार, एल्गोरिथम के प्रथम चरण में O(log i) समय लगता है।

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

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

विकल्प

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

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

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

अनुप्रयोग

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

यह भी देखें

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