Η κύρια διαφορά μεταξύ της γραμμικής αναζήτησης και της δυαδικής αναζήτησης είναι ότι η δυαδική αναζήτηση διαρκεί λιγότερο χρόνο για την αναζήτηση ενός στοιχείου από την ταξινομημένη λίστα στοιχείων. Επομένως, συνάγεται ότι η αποτελεσματικότητα της δυαδικής μεθόδου αναζήτησης είναι μεγαλύτερη από την γραμμική αναζήτηση.
Μια άλλη διαφορά μεταξύ των δύο είναι ότι υπάρχει προϋπόθεση για τη δυαδική αναζήτηση, δηλαδή τα στοιχεία πρέπει να ταξινομηθούν ενώ σε γραμμική αναζήτηση δεν υπάρχει τέτοια προϋπόθεση. Παρόλο που και οι δύο μέθοδοι αναζήτησης χρησιμοποιούν διαφορετικές τεχνικές που συζητούνται παρακάτω.
Συγκριτικό διάγραμμα
| Βάση σύγκρισης | Γραμμική αναζήτηση | Δυαδική αναζήτηση |
|---|---|---|
| Χρόνος Πολυπλοκότητα | ΕΠΙ) | Ο (log 2Ν) |
| Η καλύτερη περίπτωση | Πρώτο Στοιχείο O (1) | Κέντρο Στοιχείου O (1) |
| Προϋπόθεση για έναν πίνακα | Δεν απαιτείται | Η σειρά πρέπει να είναι ταξινομημένη |
| Χειρότερη περίπτωση για τον αριθμό N στοιχείων | Οι συγκρίσεις N απαιτούνται | Μπορεί να ολοκληρωθεί μετά από μόνο 2 N σύγκριση log |
| Μπορεί να εφαρμοστεί την | Λίστα πίνακα και συνδεδεμένη | Δεν είναι δυνατή η απευθείας εφαρμογή σε συνδεδεμένη λίστα |
| Εισαγωγή λειτουργίας | Εισάγεται εύκολα στο τέλος της λίστας | Απαίτηση επεξεργασίας για να εισαγάγετε στη σωστή θέση για να διατηρήσετε μια λίστα ταξινομημένων. |
| Αλγόριθμος τύπου | Επαναληπτική στη φύση | Διαχωρίστε και κατακτήστε τη φύση |
| Χρησιμότητα | Εύκολο στη χρήση και χωρίς ανάγκη για παραγγελθέντα στοιχεία. | Οποιοσδήποτε δύσκολος αλγόριθμος και στοιχεία θα πρέπει να οργανώνονται στη σειρά. |
| Γραμμές κώδικα | Πιο λιγο | Περισσότερο |
Ορισμός της γραμμικής αναζήτησης
Σε μια γραμμική αναζήτηση, κάθε στοιχείο μιας συστοιχίας ανακτάται ένα προς ένα με λογική σειρά και ελέγχεται εάν είναι επιθυμητό στοιχείο ή όχι. Μια αναζήτηση θα είναι ανεπιτυχής εάν έχουν πρόσβαση σε όλα τα στοιχεία και δεν έχει βρεθεί το επιθυμητό στοιχείο. Στη χειρότερη περίπτωση, ο αριθμός μιας μέσης περίπτωσης ίσως χρειαστεί να σαρώσουμε το μισό μέγεθος του πίνακα (n / 2).
Επομένως, η γραμμική αναζήτηση μπορεί να οριστεί ως η τεχνική που διασχίζει τη συστοιχία διαδοχικά για να εντοπίσει το δεδομένο στοιχείο. Το παρακάτω πρόγραμμα παρουσιάζει την αναζήτηση ενός στοιχείου της συστοιχίας χρησιμοποιώντας την αναζήτηση.
Αποτελεσματικότητα της γραμμικής αναζήτησης
Η κατανάλωση χρόνου ή ο αριθμός των συγκρίσεων που έγιναν κατά την αναζήτηση μιας εγγραφής σε έναν πίνακα αναζήτησης καθορίζει την αποτελεσματικότητα της τεχνικής. Εάν η επιθυμητή εγγραφή υπάρχει στην πρώτη θέση του πίνακα αναζήτησης, τότε γίνεται μόνο μία σύγκριση. Όταν η επιθυμητή εγγραφή είναι η τελευταία, πρέπει να γίνουν συγκρίσεις. Εάν η εγγραφή πρόκειται να παρουσιαστεί κάπου στον πίνακα αναζήτησης, κατά μέσο όρο, ο αριθμός των συγκρίσεων θα είναι (n + 1/2). Η χειρότερη περίπτωση απόδοσης αυτής της τεχνικής είναι το Ο (n) σημαίνει τη σειρά εκτέλεσης.
C Πρόγραμμα για την αναζήτηση ενός στοιχείου με τεχνική γραμμικής αναζήτησης.
#include #include κενό κύρια () {int a [100], n, i, στοιχείο, θέση = -1; clrscr (); printf ("\ nΕπιλέξτε τον αριθμό του στοιχείου:"); scanf ("% d", & n); printf ("Εισάγετε τους αριθμούς: \ n"); για (i = 0, i <= n-1, i ++) {scanf ("% d", & a [i]); } printf ("\ nΕπιλογή του αριθμού που θα αναζητηθεί:"); scanf ("% d", & στοιχείο); για (i = 0, i = 0) {printf ("% d:", θέση, θέση + 1); } else {printf ("\ n Αντικείμενο δεν υπάρχει"); } getch (); }} Ορισμός της δυαδικής αναζήτησης
Η δυαδική αναζήτηση είναι ένας εξαιρετικά αποτελεσματικός αλγόριθμος. Αυτή η τεχνική αναζήτησης καταναλώνει λιγότερο χρόνο στην αναζήτηση του δεδομένου αντικειμένου σε ελάχιστες δυνατές συγκρίσεις. Για να γίνει η δυαδική αναζήτηση, πρώτα, πρέπει να ταξινομήσουμε τα στοιχεία συστοιχίας.
Η λογική πίσω από αυτή την τεχνική δίνεται παρακάτω:
- Πρώτον, βρείτε το μεσαίο στοιχείο του πίνακα.
- Το μεσαίο στοιχείο της συστοιχίας συγκρίνεται με το στοιχείο προς αναζήτηση.
Μπορεί να προκύψουν τρεις περιπτώσεις:
- Αν το στοιχείο είναι το απαιτούμενο στοιχείο, τότε η αναζήτηση είναι επιτυχής.
- Όταν το στοιχείο είναι μικρότερο από το επιθυμητό στοιχείο, αναζητήστε μόνο το πρώτο μισό του πίνακα.
- Αν είναι μεγαλύτερο από το επιθυμητό στοιχείο, τότε αναζητήστε στο δεύτερο μισό του πίνακα.
Επαναλάβετε τα ίδια βήματα μέχρι να βρεθεί ή εξαντληθεί ένα στοιχείο στην περιοχή αναζήτησης. Σε αυτόν τον αλγόριθμο, κάθε φορά που μειώνεται η περιοχή αναζήτησης. Επομένως ο αριθμός των συγκρίσεων είναι το πολύ log (N + 1). Ως αποτέλεσμα, είναι ένας αποτελεσματικός αλγόριθμος σε σύγκριση με τη γραμμική αναζήτηση, αλλά ο πίνακας πρέπει να ταξινομηθεί πριν γίνει η δυαδική αναζήτηση.
C Πρόγραμμα για να βρείτε ένα στοιχείο με δυαδική τεχνική αναζήτησης.
#include κενό main () {int i, beg, end, μέση, n, αναζήτηση, πίνακας [100]; printf ("Εισάγετε τον αριθμό του στοιχείου \ n"); scanf ("% d", & n); printf ("Εισάγετε τους% d αριθμούς \ n", n); για το (i = 0; i <n; i ++) scanf ("% d", & array [i]); printf ("Εισάγετε τον αριθμό προς αναζήτηση \ n"); scanf ("% d", & αναζήτηση); beg = 0; άκρο = η - 1; μέση = (beg + τέλος) / 2; ενώ (beg <= end) {if (array [mid] end) printf ("Η αναζήτηση είναι ανεπιτυχής!% d δεν υπάρχει στη λίστα. \ n", αναζήτηση); getch (); }} Βασικές διαφορές μεταξύ γραμμικής αναζήτησης και δυαδικής αναζήτησης
- Η γραμμική αναζήτηση έχει επαναληπτικό χαρακτήρα και χρησιμοποιεί διαδοχική προσέγγιση. Από την άλλη πλευρά, οι δυαδικές εφαρμογές αναζήτησης διαχωρίζουν και κατακτούν την προσέγγιση.
- Η χρονική πολυπλοκότητα της γραμμικής αναζήτησης είναι O (N) ενώ η δυαδική αναζήτηση έχει O (log 2 N).
- Ο καλύτερος χρόνος για την περίπτωση γραμμικής αναζήτησης είναι για το πρώτο στοιχείο δηλαδή O (1). Αντιθέτως, σε δυαδική αναζήτηση, είναι για το μεσαίο στοιχείο, δηλαδή O (1).
- Στη γραμμική αναζήτηση, η χειρότερη περίπτωση για την αναζήτηση ενός στοιχείου είναι ο αριθμός N σύγκρισης. Αντίθετα, είναι log 2 N αριθμός σύγκρισης για δυαδική αναζήτηση.
- Η γραμμική αναζήτηση μπορεί να εφαρμοστεί σε έναν πίνακα καθώς και σε μια συνδεδεμένη λίστα, ενώ η δυαδική αναζήτηση δεν μπορεί να εφαρμοστεί απευθείας σε συνδεδεμένη λίστα.
- Όπως γνωρίζουμε, η δυαδική αναζήτηση απαιτεί την ταξινομημένη συστοιχία που είναι λόγος. Απαιτείται επεξεργασία για να εισαχθεί στην κατάλληλη θέση της για να διατηρήσει μια ταξινομημένη λίστα. Αντίθετα, η γραμμική αναζήτηση δεν απαιτεί ταξινομημένα στοιχεία, επομένως τα στοιχεία εισάγονται εύκολα στο τέλος της λίστας.
- Η γραμμική αναζήτηση είναι εύκολη στη χρήση και δεν υπάρχει ανάγκη για παραγγελθέντα στοιχεία. Από την άλλη πλευρά, ο δυαδικός αλγόριθμος αναζήτησης είναι δύσκολος και τα στοιχεία είναι απαραίτητα ρυθμισμένα στη σειρά.
συμπέρασμα
Τόσο οι γραμμικοί όσο και οι δυαδικοί αλγόριθμοι αναζήτησης μπορούν να είναι χρήσιμοι ανάλογα με την εφαρμογή. Όταν ένας πίνακας είναι η δομή δεδομένων και τα στοιχεία διατάσσονται σε ταξινομημένη σειρά, τότε η δυαδική αναζήτηση προτιμάται για γρήγορη αναζήτηση. Εάν η συνδεδεμένη λίστα είναι η δομή δεδομένων ανεξάρτητα από τον τρόπο με τον οποίο τα στοιχεία είναι διευθετημένα, η γραμμική αναζήτηση υιοθετείται λόγω της έλλειψης άμεσης εφαρμογής του δυαδικού αλγορίθμου αναζήτησης.
Ο τυπικός δυαδικός αλγόριθμος αναζήτησης δεν μπορεί να χρησιμοποιηθεί στη συνδεδεμένη λίστα, επειδή η συνδεδεμένη λίστα είναι δυναμική στη φύση και δεν είναι γνωστό πού ανατίθεται στην πραγματικότητα το μεσαίο στοιχείο. Ως εκ τούτου, υπάρχει η απαίτηση να σχεδιαστεί η παραλλαγή του δυαδικού αλγορίθμου αναζήτησης που μπορεί να λειτουργήσει σε συνδεδεμένη λίστα επίσης διότι η δυαδική αναζήτηση είναι ταχύτερη στην εκτέλεση από μια γραμμική αναζήτηση.
