Unlimited Plugins, WordPress themes, videos & courses! Unlimited asset downloads! From $16.50/m
Advertisement
  1. Code
  2. Algorithms
Code

Ο δυαδικός αλγόριθμος αναζήτησης στην JavaScript

by
Difficulty:IntermediateLength:MediumLanguages:

Greek (ελληνικά) translation by Merianos Nikos (you can also view the original English article)

Σε αυτό το άρθρο, θα συγκρίνω τον αλγόριθμο γραμμικής αναζήτησης και τον αλγόριθμο δυαδικής αναζήτησης.

Εισαγωγή

Ως προγραμματιστής, θέλετε να βρείτε την καλύτερη λύση σε ένα πρόβλημα, έτσι ώστε ο κώδικας σας είναι όχι μόνο σωστός αλλά και αποτελεσματικός. Η επιλέγοντας ενός ακατάλληλου αλγόριθμου θα μπορούσε να σημαίνει μεγαλύτερο χρόνο ολοκλήρωσης, αυξημένη πολυπλοκότητα στον κώδικα ή ακόμα χειρότερα ένα πρόγραμμα που σπάει. Ενδέχεται να έχετε χρησιμοποιήσει έναν αλγόριθμο αναζήτησης για να εντοπίσετε αντικείμενα σε μια συλλογή δεδομένων. Η γλώσσα JavaScript έχει αρκετές μεθόδους, όπως η find, για να εντοπίσετε στοιχεία σε ένα πίνακα. Ωστόσο, αυτές οι μέθοδοι χρησιμοποιούν γραμμική αναζήτηση. Ένας αλγόριθμος γραμμική αναζήτηση ξεκινά στην αρχή μιας λίστας και συγκρίνει κάθε στοιχείο με την τιμή αναζήτησης, μέχρι να βρεθεί. Αυτή η προσέγγιση είναι μια χαρά, όταν έχετε έναν μικρό αριθμό στοιχείων. Αλλά όταν πραγματοποιείτε αναζήτηση σε μεγάλες λίστες που έχουν χιλιάδες ή εκατομμύρια στοιχεία χρειάζεστε έναν καλύτερο τρόπο για να εντοπίσετε στοιχεία. Αυτή είναι και η περίπτωση στην οποία θα χρειαστείτε την δυαδική αναζήτηση. Σε αυτό το σεμινάριο, θα σας εξηγήσω πώς η δυαδική αναζήτηση λειτουργεί και πώς θα εφαρμόσετε τον αλγόριθμο στην JavaScript. Πρώτον, θα εξετάσουμε τον αλγόριθμο γραμμική αναζήτηση.

Γραμμική Αναζήτηση

Θα ξεκινήσουμε εξηγώντας πώς να πραγματοποιήσετε γραμμική αναζήτηση στην JavaScript. Θα δημιουργήσουμε μια συνάρτηση που ονομάζεται linearSearch η οποία δέχεται ως παραμέτρους μια τιμή που είναι ένας ακέραιος ή μια συμβολοσειρά και έναν πίνακα. Η συνάρτηση θα αναζήτηση κάθε στοιχείου του πίνακα για την τιμή και θα επιστρέφει τη θέση της τιμής στον πίνακα αν βρεθεί. Εάν η τιμή δεν είναι στον πίνακα, θα επιστρέψει -1. Για παράδειγμα, καλώντας linearSearch (1, [3, 4, 2, 1, 5]) θα επιστρέψει 3 και καλώντας linearSearch (0, [3, 4, 2, 1, 5]) θα επιστρέψει -1.

Αυτός είναι ο ψευδοκώδικας της συνάρτησης:

Υλοποίηση της γραμμικής αναζήτησης στην JavaScript

Αυτή είναι μια υλοποίηση του αλγόριθμου γραμμικής αναζήτησης στην JavaScript:

Είναι σημαντικό να σημειωθεί ότι ο αλγόριθμος γραμμική αναζήτηση δεν είναι απαραίτητο να χρησιμοποιήσει μια ταξινομημένη λίστα. Επίσης, ο αλγόριθμος μπορεί να προσαρμοστεί για χρήση σε διαφορετικά σενάρια, όπως για παράδειγμα να ψάχνει για έναν πίνακα αντικειμένων βάση κλειδιού. Εάν έχετε έναν πίνακα με δεδομένων πελατών που περιλαμβάνει κλειδιά για το όνομα και το επώνυμο, μπορείτε να δείτε αν ο πίνακας έχει έναν πελάτη με ένα καθορισμένο όνομα. Σε αυτή την περίπτωση, αντί να ελέγξετε αν το list[index] είναι ίση με την τιμή αναζήτησης, θα ελέγξετε για list[index].first.

Στο παραπάνω παράδειγμα, χρησιμοποίησα την συνάρτηση linearSearch σε έναν πίνακα με τα 5 στοιχεία. Στη χειρότερη περίπτωση, όταν η τιμή αναζήτησης δεν είναι στη λίστα ή η τιμή είναι στο τέλος της λίστας, η συνάρτηση θα πρέπει να κάνει 5 συγκρίσεις. Επειδή ο πίνακας μας είναι πολύ μικρός δεν υπάρχει καμία ανάγκη για βελτιστοποίηση χρησιμοποιώντας ένα διαφορετικό αλγόριθμο. Ωστόσο, μετά από ένα ορισμένο σημείο, δεν είναι πλέον αποτελεσματική η χρήση του γραμμικού αλγόριθμου αναζήτησης και έτσι ίσως είναι καλύτερο να χρησιμοποιηθεί ο αλγόριθμός δυαδικής αναζήτησης.

Δυαδική Αναζήτηση

Φανταστείτε ότι παίζετε ένα παιχνίδι που πρέπει να μαντέψετε αριθμούς. Στο παιχνίδι αυτό σας ζητούν να μαντέψετε έναν αριθμό μεταξύ 1 και 100. Εάν ο αριθμός σας είναι πάρα πολύ μεγάλος ή πολύ μικρός, θα σας το πουν. Ποια θα είναι η στρατηγική σας; Θα επιλέξετε τυχαία αριθμούς; Θα ξεκινήσετε με το 1, μετά το 2, και ούτω καθεξής μέχρι να μαντέψατε σωστά; Ακόμα και αν είχατε απεριόριστη προσπάθειες, θα πρέπει να κάνετε τη σωστή μαντεψιά σε όσο το δυνατόν λιγότερες προσπάθειες. Επομένως, θα μπορούσατε να αρχίσετε με το 50. Αν ο αριθμός είναι υψηλότερος εσείς θα μπορούσε να μαντέψετε το 75. Αν είναι χαμηλότερο, τότε αυτό σημαίνει ότι ο αριθμός είναι μεταξύ 50 και 75 και θα μπορείτε να επιλέξετε έναν αριθμό που είναι στη μέση. Μπορείτε να συνεχίσετε έτσι, μέχρις ότου βρείτε το σωστό αριθμό. Αυτό είναι παρόμοιο με το πώς λειτουργεί η δυαδική αναζήτηση.

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

Για αναζήτηση του 9 στην λίστα:

Βρίσκουμε πρώτα το μεσαίο στοιχείο. Αυτό είναι το στοιχείο στη θέση Math.floor ((first + last)/2) όπου first είναι ο πρώτος δείκτης και last είναι ο τελευταίος δείκτης. Επιλέγουμε να στρογγυλοποιήσουμε προς τα κάτω, έτσι ώστε αν το αποτέλεσμα είναι ένα κλάσμα να μετατραπεί σε έναν ακέραιο αριθμό. Το μεσαίο στοιχείο σε αυτήν τη λίστα είναι το 5. Η τιμή αναζήτησης 9 είναι μεγαλύτερη από 5 έτσι αναζητούμε τη λίστα:

Το μεσαίο στοιχείο σε αυτό το τμήμα είναι το 8. Το εννέα είναι μεγαλύτερη από το 8, έτσι αναζητούμε τη λίστα:

Το μεσαίο στοιχείο είναι 9, έτσι μπορούμε να σταματήσουμε την αναζήτησή μας εδώ.

Ακολουθεί ο ψευδο-κώδικας που εκφράζει τον παραπάνω αλγόριθμο για δυαδική αναζήτηση:

Υλοποίηση της δυαδικής αναζήτησης σε JavaScript

Τώρα ας γράψουμε τον δυαδικό αλγόριθμο αναζήτησης σε JavaScript!

Θα δημιουργήσουμε μια συνάρτηση, binarySearch, που δέχεται μια τιμή και ένα πίνακα ως παραμέτρους. Θα επιστρέψει ο δείκτης όπου παρουσιάζεται η τιμή στη λίστα αν βρεθεί. Εάν η τιμή δεν υπάρχει θα επιστρέφει -1. Αυτή είναι η υλοποίηση γραμμένη σε JavaScript:

Συμπέρασμα

Σε αυτό το tutorial, είδαμε πώς να εφαρμόσουν μια γραμμική αναζήτηση και τον αλγόριθμο δυαδικής αναζήτησης. Ο αλγόριθμος γραμμική αναζήτηση είναι πιο απλός και δεν απαιτεί ένα ταξινομημένο πίνακα. Ωστόσο, είναι ανεπαρκής για να χρησιμοποιηθεί σε μεγαλύτερους πίνακες. Στη χειρότερη περίπτωση, ο αλγόριθμος θα πραγματοποιήσει αναζήτηση σε n στοιχεία κάνοντας σύγκριση (όπου n είναι ο αριθμός των στοιχείων).

Ο αλγόριθμος δυαδική αναζήτηση, από την άλλη πλευρά, απαιτεί να ταξινομήσετε τον πίνακα πρώτα και είναι πιο περίπλοκος στην εφαρμογή του. Ωστόσο, είναι πιο αποτελεσματικός ακόμη και όταν λαμβάνοντας υπόψη το κόστος της ταξινόμησης. Για παράδειγμα, σε ένα πίνακα με 10 στοιχεία θα χρειαστούν το πολύ 4 συγκρίσεις με δυαδική αναζήτηση σε αντίθεση με 10 συγκρίσεις της γραμμικής αναζήτηση — δεν είναι και μεγάλη βελτίωση. Ωστόσο, για έναν πίνακα με 1.000.000 στοιχεία η χειρότερη περίπτωση με δυαδική αναζήτηση είναι μόνο 20 συγκρίσεις. Αυτό είναι μια τεράστια βελτίωση σε σχέση με τη γραμμική Αναζήτηση!

Το να γνωρίζετε πως να χρησιμοποιήσετε την δυαδική αναζήτηση, δεν είναι κάτι που θα σας φανεί χρήσιμο μόνο σε μια συνέντευξη για δουλεία. Είναι μια πρακτική δεξιότητα που μπορεί να κάνει τον κώδικα σας να λειτουργεί πολύ ποιο αποδοτικά.

Advertisement
Advertisement
Advertisement
Advertisement
Looking for something to help kick start your next project?
Envato Market has a range of items for sale to help get you started.