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

() translation by (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.

Αυτός είναι ο ψευδοκώδικας της συνάρτησης:

Set found to false
Set position to −1
Set index to 0
while found is false and index < number of elements
    if list[index] is equal to search value
        Set found to true
        Set position to index
    else Add 1 to index
return position

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

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

function linearSearch(value, list) {
    let found = false;
    let position = -1;
    let index = 0;

    while(!found && index < list.length) {
        if(list[index] == value) {
            found = true;
            position = index;
        } else {
            index += 1;
        }
    }
    return position;
}

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

Στο παραπάνω παράδειγμα, χρησιμοποίησα την συνάρτηση linearSearch σε έναν πίνακα με τα 5 στοιχεία. Στη χειρότερη περίπτωση, όταν η τιμή αναζήτησης δεν είναι στη λίστα ή η τιμή είναι στο τέλος της λίστας, η συνάρτηση θα πρέπει να κάνει 5 συγκρίσεις. Επειδή ο πίνακας μας είναι πολύ μικρός δεν υπάρχει καμία ανάγκη για βελτιστοποίηση χρησιμοποιώντας ένα διαφορετικό αλγόριθμο. Ωστόσο, μετά από ένα ορισμένο σημείο, δεν είναι πλέον αποτελεσματική η χρήση του γραμμικού αλγόριθμου αναζήτησης και έτσι ίσως είναι καλύτερο να χρησιμοποιηθεί ο αλγόριθμός δυαδικής αναζήτησης.

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

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

Σε αντίθεση με την γραμμική αναζήτηση, η δυαδική αναζήτηση χρησιμοποιεί μια ταξινομημένη λίστα. Για να αναζητήσετε μια τιμή, πρώτα συγκρίνετε την τιμή με το μεσαίο στοιχείο της λίστας. Αν είναι ίσες, η τιμή αναζήτησης έχει βρεθεί. Εάν η τιμή είναι μεγαλύτερη από το μεσαίο στοιχείο, μπορείτε να αναζητήσετε το επάνω μισό των δεδομένων. Στη συνέχεια, συγκρίνετε το μεσαίο στοιχείο αυτής της ενότητας με την τιμή αναζήτησης. Εναλλακτικά, εάν το στοιχείο είναι μικρότερο από το μεσαίο στοιχείο, κάνετε αναζήτηση στο κάτω μισό της λίστας και να συγκρίνετε την μέση τιμή. Ο κατάλογος χωρίζεται επανειλημμένα στο μισό μέχρι το στοιχείο να βρεθεί ή να μην υπάρχουν άλλα στοιχεία για αναζήτηση.

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

1	1 2 3 4 5 6 7 8 9 10

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

1	6 7 8 9 10

Το μεσαίο στοιχείο σε αυτό το τμήμα είναι το 8. Το εννέα είναι μεγαλύτερη από το 8, έτσι αναζητούμε τη λίστα:

9 10

Το μεσαίο στοιχείο είναι 9, έτσι μπορούμε να σταματήσουμε την αναζήτησή μας εδώ.

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

Set first to 0
Set last to the last index in the list
Set found to false
Set position to −1
while found is false and first is less than or equal to last
    Set middle to the index halfway between first and last
    if list[middle] equals the desired value
        Set found to true
        Set position to middle
    else if list[middle] is greater than the desired value
        Set last to middle − 1
    else
        Set first to middle + 1
return position

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

Τώρα ας γράψουμε τον δυαδικό αλγόριθμο αναζήτησης σε JavaScript!

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

function binarySearch(value, list) {
    let first = 0;    //left endpoint
    let last = list.length - 1;   //right endpoint
    let position = -1;
    let found = false;
    let middle;

    while (found === false && first <= last) {
        middle = Math.floor((first + last)/2);
        if (list[middle] == value) {
            found = true;
            position = middle;
        } else if (list[middle] > value) {  //if in lower half
            last = middle - 1;
        } else {  //in in upper half
            first = middle + 1;
        }
    }
    return position;
}


Συμπέρασμα

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

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

Το να γνωρίζετε πως να χρησιμοποιήσετε την δυαδική αναζήτηση, δεν είναι κάτι που θα σας φανεί χρήσιμο μόνο σε μια συνέντευξη για δουλεία. Είναι μια πρακτική δεξιότητα που μπορεί να κάνει τον κώδικα σας να λειτουργεί πολύ ποιο αποδοτικά.