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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

चरण 5) इंडेक्स = i (चूंकि आइटम इंडेक्स संख्या i पर पाया जाता है)। चरण 8 पर जाएँ।

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

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

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

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

अनुक्रमिक खोज एल्गोरिथ्म के लिए छद्म कोड

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 negative index is not valid
return -1

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(arr[0]);
    int item;
    cout << "Enter a number to search: ";
    cin >> item;
    int idx = linearSearch(arr, 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 कोड उदाहरण रैखिक खोज

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) डेटा [5] और डेटा [4] को स्वैप करें। फिर डेटा सरणी इस तरह दिखाई देगी:

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

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

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

इस विधि में, हम 0वें इंडेक्स में खोज तत्व को स्वैप करते हैं। क्योंकि अगर इसे फिर से खोजा जाता है, तो हम इसे O(1) समय पर पा सकते हैं।

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

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

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