Γραμμική αναζήτηση: Python, C++ Παράδειγμα
Σάρα Τσεν
Τι είναι ο αλγόριθμος αναζήτησης;
Ένας αλγόριθμος αναζήτησης έχει σχεδιαστεί για να βρίσκει ένα στοιχείο ή ένα αντικείμενο από μια συλλογή στοιχείων ή αντικειμένων με μια δεδομένη δομή δεδομένων. Για παράδειγμα, αναζητήστε το ελάχιστο ύψος από μια δεδομένη λίστα υψών ή αναζητήστε την υψηλότερη βαθμολογία από μια λίστα ή έναν πίνακα αριθμών. Λίγοι δημοφιλείς αλγόριθμοι αναζήτησης περιλαμβάνουν «Γραμμική αναζήτηση», «Δυαδική αναζήτηση», «Αναζήτηση μετάβασης», «Αναζήτηση Fibonacci» κ.λπ.
Τι είναι η Γραμμική αναζήτηση;
Η γραμμική αναζήτηση είναι ένας από τους απλούστερους αλγόριθμους αναζήτησης. Από μια δεδομένη λίστα ή πίνακα, αναζητά το δεδομένο στοιχείο ένα προς ένα. Η Γραμμική Αναζήτηση επαναλαμβάνεται σε ολόκληρη τη λίστα και ελέγχει εάν κάποιο συγκεκριμένο στοιχείο είναι ίσο με το στοιχείο αναζήτησης. Ονομάζεται επίσης το διαδοχική αναζήτηση.
Τι κάνει η γραμμική συνάρτηση αναζήτησης;
Ένας πίνακας ακεραίων δίνεται ως "Numbers, και μια μεταβλητή "item" περιέχει τον ακέραιο αριθμό προς αναζήτηση.
Τώρα, ο αλγόριθμος Γραμμικής αναζήτησης μπορεί να παρέχει την ακόλουθη έξοδο:
- "-1"; Αυτό σημαίνει ότι το δεδομένο στοιχείο δεν βρίσκεται στον πίνακα
- Οποιοσδήποτε αριθμός μεταξύ 0 και n-1. σημαίνει ότι βρέθηκε το στοιχείο αναζήτησης και επιστρέφει το ευρετήριο του στοιχείου στον πίνακα. Εδώ, το "n" αντιπροσωπεύει το μέγεθος του πίνακα.
Πώς λειτουργεί η Γραμμική Αναζήτηση;
Ας πούμε έναν πίνακα που περιέχει ακέραιους αριθμούς. Η εργασία είναι να βρείτε έναν δεδομένο αριθμό στον πίνακα.
- Εάν ο αριθμός βρίσκεται στον πίνακα, πρέπει να επιστρέψουμε το ευρετήριο αυτού του αριθμού.
- Εάν ο δεδομένος αριθμός δεν βρεθεί, τότε θα επιστρέψει -1.
Στο διάγραμμα ροής, το "Data" είναι ο ακέραιος πίνακας, το "N" είναι το μέγεθος του πίνακα και το "item" είναι ο αριθμός που θέλουμε να αναζητήσουμε στον πίνακα.
Διάγραμμα ροής για αλγόριθμο γραμμικής αναζήτησης:
Ακολουθούν τα βήματα του διαγράμματος ροής:
Βήμα 1) Διαβάστε το στοιχείο αναζήτησης, "αντικείμενο".
Βήμα 2) Εκκίνηση i=0 και δείκτης=-1
Βήμα 3) Αν εγώ
Βήμα 4) Εάν το Data[i] ισούται με το "item", τότε μεταβείτε στο βήμα 5. Διαφορετικά μεταβείτε στο βήμα 6.
Βήμα 5) Ευρετήριο = i (Καθώς το είδος βρίσκεται στο ευρετήριο αριθ. i). Μεταβείτε στο βήμα 8.
Βήμα 6) i = i +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 για την εκτέλεση μιας συγκεκριμένης εργασίας. Στον αλγόριθμο γραμμικής αναζήτησης, η εργασία είναι να βρείτε το κλειδί αναζήτησης από το στοιχείο του πίνακα.
Τρεις τύποι χρονικής πολυπλοκότητας είναι:
- Στη χειρότερη περίπτωση
- καλυτερα Case Scenario
- Μέσο σενάριο περίπτωσης
Χρονική πολυπλοκότητα γραμμικής αναζήτησης στο χειρότερο σενάριο:
Ας πούμε, πρέπει να εκτελέσουμε μια γραμμική αναζήτηση σε έναν πίνακα με μέγεθος "n". Μπορούμε να βρούμε το αντικείμενο αναζήτησης μεταξύ του ευρετηρίου 0 έως n-1. Στη χειρότερη περίπτωση, ο αλγόριθμος θα προσπαθήσει να αντιστοιχίσει όλα τα στοιχεία από τον πίνακα με το στοιχείο αναζήτησης.
Σε αυτή την περίπτωση, η πολυπλοκότητα στη χειρότερη περίπτωση θα είναι O(n). Εδώ, "O"-big O Notation σημαίνει τη συνάρτηση πολυπλοκότητας.
Χρονική πολυπλοκότητα γραμμικής αναζήτησης σε σενάριο καλυτέρων:
Ας υποθέσουμε ότι αναζητούμε ένα στοιχείο που βρίσκεται στην πρώτη θέση του πίνακα. Σε αυτό το σενάριο, ο αλγόριθμος γραμμικής αναζήτησης δεν θα πραγματοποιήσει αναζήτηση για όλα τα n στοιχεία του πίνακα. Άρα η πολυπλοκότητα θα είναι Ο(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).
Εφαρμογή Αλγορίθμου Γραμμικής Αναζήτησης
Ακολουθούν ορισμένες εφαρμογές γραμμικής αναζήτησης που μπορούμε να χρησιμοποιήσουμε.
- Για πίνακες μικρού μεγέθους ή μόνο μερικά στοιχεία στη λίστα, είναι ευκολότερο να χρησιμοποιήσετε τη γραμμική αναζήτηση.
- Η μέθοδος γραμμικής αναζήτησης μπορεί να χρησιμοποιηθεί σε μονή ή πολυδιάστατους πίνακες ή άλλες δομές δεδομένων.
- Γενικά, η γραμμική αναζήτηση είναι απλή και αποτελεσματική για την εκτέλεση αναζήτησης στα «μη διατεταγμένα» δεδομένα. Μπορούμε να ανακτήσουμε ένα μεμονωμένο δεδομένα από τη δεδομένη μη ταξινομημένη λίστα εύκολα.
