रेखीय खोज: Python, C++ उदाहरण

खोज एल्गोरिथ्म क्या है?

एक खोज एल्गोरिदम को किसी दिए गए डेटा संरचना में मौजूद तत्वों या वस्तुओं के संग्रह से किसी तत्व या वस्तु को खोजने के लिए डिज़ाइन किया जाता है। उदाहरण के लिए, ऊंचाइयों की दी गई सूची में से न्यूनतम ऊंचाई खोजना, या संख्याओं की सूची या सरणी में से उच्चतम अंक खोजना। कुछ लोकप्रिय खोज एल्गोरिदम में "रेखीय खोज", "द्विआधारी खोज", "कूद खोज", "फिबोनाची खोज" आदि शामिल हैं।

रैखिक खोज क्या है?

रैखिक खोज यह सबसे सरल खोज एल्गोरिदम में से एक है। दी गई सूची या ऐरे में से, यह दिए गए तत्व को एक-एक करके खोजता है। रैखिक खोज पूरी सूची पर पुनरावृति करती है और जाँचती है कि क्या कोई विशेष तत्व खोजे जा रहे तत्व के बराबर है। इसे रैखिक खोज भी कहा जाता है। अनुक्रमिक खोज.

रेखीय खोज फ़ंक्शन क्या करता है?

पूर्णांकों की एक सरणी इस प्रकार दी गई है “Numbers, " और एक चर "आइटम" में खोजने के लिए पूर्णांक संख्या होती है।

अब, रैखिक खोज एल्गोरिथ्म निम्नलिखित आउटपुट प्रदान कर सकता है:

• “-1”; इसका मतलब है कि दिया गया तत्व ऐरे में नहीं मिला।
• 0 से n-1 के बीच की कोई भी संख्या; इसका मतलब है कि खोज तत्व मिल गया है, और यह सरणी पर तत्व का सूचकांक लौटाता है। यहाँ, "n" सरणी के आकार को दर्शाता है।

रेखीय खोज कैसे काम करती है?

मान लीजिए हमारे पास पूर्णांक संख्याओं का एक ऐरे है। कार्य यह है कि ऐरे में दी गई संख्या को ढूँढ़ना है।

• यदि संख्या सरणी में स्थित है, तो हमें उस संख्या का सूचकांक लौटाना होगा।
• यदि दी गई संख्या नहीं मिलती है, तो यह -1 लौटाएगा।

फ्लोचार्ट में, "डेटा" पूर्णांक सरणी है, "एन" सरणी का आकार है, और "आइटम" वह संख्या है जिसे हम सरणी में खोजना चाहते हैं।

रेखीय खोज एल्गोरिथ्म के लिए फ़्लोचार्ट:

फ्लोचार्ट के चरण इस प्रकार हैं:

चरण 1) खोज आइटम, “आइटम” पढ़ें।

चरण 2) i=0 और index=-1 से आरंभ करें।

चरण 3) अगर मुझे

चरण 4) यदि डेटा[i] “आइटम” के बराबर है, तो चरण 5 पर जाएँ। अन्यथा चरण 6 पर जाएँ।

चरण 5) सूचकांक = i (क्योंकि वस्तु सूचकांक संख्या i पर पाई गई है)। चरण 8 पर जाएं।

चरण 6) मैं = मैं +1.

चरण 7) चरण 3 पर जाएं।

चरण 8) बंद करो.

सरलता के लिए, हम पूर्णांकों की एक सरणी के साथ एक उदाहरण प्रदान करते हैं। रैखिक खोज स्ट्रिंग, ऑब्जेक्ट्स की एक सरणी या संरचना में भी लागू होती है।

उपनाम Code अनुक्रमिक खोज एल्गोरिथम के लिए

नीचे दिया गया स्यूडोकोड ऊपर वर्णित लीनियर सर्च के लॉजिक को दर्शाता है। यह एरे में पहले इंडेक्स से शुरू होता है और मिलान होने पर उसकी स्थिति बताता है, अन्यथा -1 लौटाता है।

function linearSearch: in → Data[], item
    foundAt = -1
    for i in (0 to data.length):
        if data[i] equals item:
            // item is found in the array
            // returning the index
            return i
    // item not found in the array
    // -1 means no item found, as a negative index is not valid
    return -1

C++ Code उदाहरण रेखीय खोज

यहाँ एक पूर्ण है C++ यह प्रोग्राम अनुक्रमिक खोज को लागू करता है और खोजे गए मान का सूचकांक प्रिंट करता है।

#include <bits/stdc++.h>
using namespace std;

int linearSearch(int *arr, int item, int n) {
    int idx = -1;
    for (int i = 0; i < n; i++) {
        if (arr[i] == item) {
            idx = i;
            break;
        }
    }
    return idx;
}

int main() {
    int array[] = {1, 9, 8, 7, 6, 3, 11, 4, 6, 9, 7, 2, 0, 19, -10};
    int n = sizeof(array) / sizeof(array[0]);
    int item;
    cout << "Enter a number to search: ";
    cin >> item;
    int idx = linearSearch(array, item, n);
    if (idx >= 0) {
        cout << item << " is found at index " << idx << endl;
    } else {
        cout << "Could not find " << item << " in the array" << endl;
    }
}

आउटपुट:

Enter a number to search: -10
-10 is found at index 14

Python Code उदाहरण रेखीय खोज

वही तर्क Python यह सूची के इंडेक्स पर एक ही लूप का उपयोग करता है और मेल खाने वाले तत्व की स्थिति लौटाता है।

def linearSearch(data, item):
    for i in range(len(data)):
        if data[i] == item:
            return i
    return -1

data = [1, 9, 8, 7, 6, 3, 11, 4, 6, 9, 7, 2, 0, 19, -10]
item = int(input("Enter a number to search: "))
idx = linearSearch(data, item)
if idx >= 0:
    print("{} is found at index {}".format(item, idx))
else:
    print("{} was not found".format(item))

आउटपुट:

Enter a number to search: -10
-10 is found at index 14

रैखिक खोज एल्गोरिथ्म का जटिलता विश्लेषण

सामान्यतः, समय जटिलता का अर्थ है किसी निश्चित कार्य को करने में लगने वाला CPU समय। रैखिक खोज एल्गोरिदम में, कार्य सरणी के तत्वों में से खोज कुंजी को खोजना है।

समय जटिलताएं तीन प्रकार की होती हैं:

• सबसे बुरी स्थिति
• बेहतरीन परिदृश्य
• औसत मामला परिदृश्य

सबसे खराब स्थिति में रैखिक खोज की समय जटिलता:

मान लीजिए कि हमें n आकार के एक ऐरे में लीनियर सर्च करना है। हम सर्च आइटम को इंडेक्स 0 से n-1 के बीच खोज सकते हैं। सबसे खराब स्थिति में, एल्गोरिदम ऐरे के सभी तत्वों को सर्च एलिमेंट से मिलाने की कोशिश करेगा।

उस स्थिति में, सबसे खराब स्थिति में जटिलता O(n) होगी। यहाँ, "O" (बिग O नोटेशन) जटिलता फ़ंक्शन को दर्शाता है।

सर्वोत्तम स्थिति में रैखिक खोज की समय जटिलता:

मान लीजिए कि हम एक ऐसे तत्व की खोज कर रहे हैं जो ऐरे के पहले स्थान पर स्थित है। इस स्थिति में, रैखिक खोज एल्गोरिदम ऐरे के सभी n तत्वों की खोज नहीं करेगा। इसलिए जटिलता O(1) होगी। इसका अर्थ है स्थिर समय।

औसत मामले परिदृश्य में रैखिक खोज की समय जटिलता:

जब कोई तत्व सारणी के मध्य सूचकांक पर पाया जाता है, तो यह कहा जा सकता है कि रैखिक खोज के लिए औसत केस जटिलता O(N) है, जहां N का अर्थ सारणी की लंबाई है।

लीनियर सर्च एल्गोरिदम की स्पेस कॉम्प्लेक्सिटी:

लीनियर सर्च के लिए स्पेस कॉम्प्लेक्सिटी हमेशा O(N) होती है क्योंकि लीनियर सर्च फंक्शन में हमें किसी भी प्रकार के अस्थायी वेरिएबल को स्टोर करने या उपयोग करने की आवश्यकता नहीं होती है।

रैखिक खोज एल्गोरिथ्म को कैसे सुधारें

प्रोग्राम के पूरे जीवनचक्र में खोज कई बार की जा सकती है। यह भी संभव है कि हम लीनियर सर्च एल्गोरिदम चला रहे हों और किसी विशिष्ट कुंजी को कई बार खोज रहे हों। हम “बाइनरी सर्च एल्गोरिथम” यदि सरणी एक क्रमबद्ध सरणी है.

मान लें कि सरणी में 10 हज़ार संख्याएँ हैं, और लक्ष्य तत्व 5000वें इंडेक्स पर पाया जाता है। इसलिए, एल्गोरिथ्म 5000 तत्वों की तुलना करने का प्रयास करेगा। अब, तुलना करना CPU-भारी कार्य है। रैखिक खोज एल्गोरिथ्म को अनुकूलित करने के लिए, हमारे पास दो विकल्प हैं।

• स्थानांतरण
• सामने ले जाएँ

स्थानान्तरण:

इस विधि में, हम खोजे गए तत्व को सरणी में उसके पिछले तत्व से बदल देंगे। उदाहरण के लिए, मान लीजिए आपके पास निम्नलिखित जैसी एक सरणी है:

डेटा[] = {1,5,9,8,7,3,4,11}

अब, हम खोजना चाहते हैं 4. ट्रांसपोज़िशन के चरण:

चरण 1) “4” सूचकांक 6 पर पाया गया। इसमें छह तुलनाएँ हुईं।

चरण 2) डेटा[6] और डेटा[5] को स्वैप करें। फिर डेटा सरणी इस तरह दिखाई देगी:

डेटा[] = {1,5,9,8,7,4,3,11}

चरण 3) फिर से 4 खोजें। सूचकांक 5 पर मिला। इस बार इसमें पाँच तुलनाएँ हुईं।

चरण 4) data[5] और data[4] को आपस में बदल दें। तब data array इस प्रकार दिखेगा:

डेटा[] = {1,5,9,8,4,7,3,11}

अब, अगर आप ध्यान दें, तो किसी कुंजी को जितनी बार खोजा जाता है, उतना ही उसका इंडेक्स कम होता जाता है। इस प्रकार, तुलनाओं की संख्या भी कम हो जाती है।

आगे की ओर बढ़ें:

इस विधि में, हम खोज तत्व को 0वें सूचकांक पर स्वैप करते हैं। क्योंकि यदि इसे दोबारा खोजा जाता है, तो हम इसे O(1) समय में पा सकते हैं।

रेखीय खोज एल्गोरिथ्म का अनुप्रयोग

यहां कुछ रेखीय खोज अनुप्रयोग दिए गए हैं जिनका हम उपयोग कर सकते हैं।

• छोटे आकार के एरे या सूची में केवल कुछ ही तत्वों के लिए, रैखिक खोज का उपयोग करना आसान होता है।
• रैखिक खोज विधि का उपयोग एकल या बहुआयामी सरणियाँ या अन्य डेटा संरचनाएं.
• आम तौर पर, "अव्यवस्थित" डेटा में खोज करने के लिए रैखिक खोज सरल और कुशल है। हम दी गई अव्यवस्थित सूची से आसानी से एक एकल डेटा प्राप्त कर सकते हैं।

अक्सर पूछे जाने वाले प्रश्न