Γραμμική αναζήτηση: Python, C++ Παράδειγμα

Τι είναι ο αλγόριθμος αναζήτησης;

Ένας αλγόριθμος αναζήτησης έχει σχεδιαστεί για να βρίσκει ένα στοιχείο ή ένα αντικείμενο από μια συλλογή στοιχείων ή αντικειμένων με μια δεδομένη δομή δεδομένων. Για παράδειγμα, αναζητήστε το ελάχιστο ύψος από μια δεδομένη λίστα υψών ή αναζητήστε την υψηλότερη βαθμολογία από μια λίστα ή πίνακα αριθμών. Λίγοι δημοφιλείς αλγόριθμοι αναζήτησης περιλαμβάνουν τις "Γραμμική Αναζήτηση", "Δυαδική Αναζήτηση", "Αναζήτηση με Άλμα", "Αναζήτηση Fibonacci" κ.λπ.

Τι είναι η Γραμμική αναζήτηση;

Γραμμική αναζήτηση είναι ένας από τους απλούστερους αλγόριθμους αναζήτησης. Από μια δεδομένη λίστα ή πίνακα, αναζητά το δεδομένο στοιχείο ένα προς ένα. Η Γραμμική Αναζήτηση επαναλαμβάνεται σε ολόκληρη τη λίστα και ελέγχει εάν κάποιο συγκεκριμένο στοιχείο είναι ίσο με το στοιχείο αναζήτησης. Ονομάζεται επίσης διαδοχική αναζήτηση.

Τι κάνει η γραμμική συνάρτηση αναζήτησης;

Ένας πίνακας ακεραίων δίνεται ως "Numbers, και μια μεταβλητή "item" περιέχει τον ακέραιο αριθμό προς αναζήτηση.

Τώρα, ο αλγόριθμος Γραμμικής αναζήτησης μπορεί να παρέχει την ακόλουθη έξοδο:

• «-1»; αυτό σημαίνει ότι το δεδομένο στοιχείο δεν βρίσκεται στον πίνακα.
• Οποιοσδήποτε αριθμός μεταξύ 0 και n-1. σημαίνει ότι βρέθηκε το στοιχείο αναζήτησης και επιστρέφει το ευρετήριο του στοιχείου στον πίνακα. Εδώ, το "n" αντιπροσωπεύει το μέγεθος του πίνακα.

Πώς λειτουργεί η Γραμμική Αναζήτηση;

Ας υποθέσουμε ότι ένας πίνακας που περιέχει ακέραιους αριθμούς. Η εργασία είναι να βρεθεί ένας δεδομένος αριθμός στον πίνακα.

• Εάν ο αριθμός βρίσκεται στον πίνακα, πρέπει να επιστρέψουμε το ευρετήριο αυτού του αριθμού.
• Εάν ο δεδομένος αριθμός δεν βρεθεί, τότε θα επιστρέψει -1.

Στο διάγραμμα ροής, το "Data" είναι ο ακέραιος πίνακας, το "N" είναι το μέγεθος του πίνακα και το "item" είναι ο αριθμός που θέλουμε να αναζητήσουμε στον πίνακα.

Διάγραμμα ροής για αλγόριθμο γραμμικής αναζήτησης:

Ακολουθούν τα βήματα του διαγράμματος ροής:

Βήμα 1) Διαβάστε το στοιχείο αναζήτησης, "αντικείμενο".

Βήμα 2) Αρχικοποιήστε το i=0 και το index=-1.

Βήμα 3) Αν εγώ

Βήμα 4) Εάν το Data[i] ισούται με το "item", τότε μεταβείτε στο βήμα 5. Διαφορετικά μεταβείτε στο βήμα 6.

Βήμα 5) Δείκτης = i (Καθώς το στοιχείο βρίσκεται στον δείκτη αρ. i). Μεταβείτε στο βήμα 8.

Βήμα 6) i = i +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 για την εκτέλεση μιας συγκεκριμένης εργασίας. Στον αλγόριθμο γραμμικής αναζήτησης, η εργασία είναι να βρεθεί το κλειδί αναζήτησης από τα στοιχεία του πίνακα.

Τρεις τύποι χρονικής πολυπλοκότητας είναι:

• Στη χειρότερη περίπτωση
• καλυτερα Case Scenario
• Μέσο σενάριο περίπτωσης

Χρονική πολυπλοκότητα γραμμικής αναζήτησης στο χειρότερο σενάριο:

Ας υποθέσουμε ότι πρέπει να εκτελέσουμε μια γραμμική αναζήτηση σε έναν πίνακα με μέγεθος "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).

Εφαρμογή Αλγορίθμου Γραμμικής Αναζήτησης

Ακολουθούν ορισμένες εφαρμογές γραμμικής αναζήτησης που μπορούμε να χρησιμοποιήσουμε.

• Για μικρού μεγέθους πίνακες ή μόνο λίγα στοιχεία στη λίστα, είναι ευκολότερο να χρησιμοποιήσετε γραμμική αναζήτηση.
• Η μέθοδος γραμμικής αναζήτησης μπορεί να χρησιμοποιηθεί σε μονή ή πολυδιάστατους πίνακες ή άλλες δομές δεδομένων.
• Γενικά, η γραμμική αναζήτηση είναι απλή και αποτελεσματική για την εκτέλεση αναζήτησης στα «μη διατεταγμένα» δεδομένα. Μπορούμε να ανακτήσουμε ένα μεμονωμένο δεδομένα από τη δεδομένη μη ταξινομημένη λίστα εύκολα.

Συχνές Ερωτήσεις