Αναζήτηση και ταξινόμηση

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

Αναζήτηση σημαίνει να απαντήσουμε, με δεδομένα μια συλλογή και μια τιμή, αν η τιμή υπάρχει και πού. Χωρίς πληροφορία για τη διάταξη των δεδομένων, δεν υπάρχει άλλη στρατηγική από το να τα κοιτάξουμε ένα ένα: είναι η γραμμική αναζήτηση. Όταν η τιμή δεν υπάρχει, σε αυτόν τον κύκλο μαθημάτων επιστρέφουμε το values.size(), την πρώτη θέση που δεν ανήκει στο διάνυσμα: δεν είναι έγκυρος δείκτης, ώστε δεν συγχέεται με μια απάντηση, και είναι η ίδια σύμβαση που ακολουθεί η βιβλιοθήκη, όπως θα φανεί στην πέμπτη παράγραφο.

#include <cstddef>#include <print>#include <vector>​// Προσυνθήκη: καμία.// Μετασυνθήκη: επιστρέφει τον μικρότερο δείκτη i με values[i] == target,// ή values.size() αν το target δεν υπάρχει.std::size_t linearSearch(const std::vector<int>& values, int target){    // Αναλλοίωτη: το target δεν υπάρχει στα values[0], ..., values[i - 1].    for (std::size_t i{0}; i < values.size(); ++i) {        if (values[i] == target) {            return i;        }    }    return values.size();}​int main(){    const std::vector<int> codes{405, 112, 318, 207, 112, 530};    for (const int target : {207, 112, 999}) {        const std::size_t pos{linearSearch(codes, target)};        if (pos == codes.size()) {            std::println("{}: δεν υπάρχει", target);        } else {            std::println("{}: θέση {}", target, pos);        }    }}

207: θέση 3112: θέση 1999: δεν υπάρχει

Η αναλλοίωτη της γραμμής 10 δίνει την ορθότητα. Στην αρχή, με το i ίσο με 0, ισχυρίζεται κάτι για ένα κενό κομμάτι και είναι αληθής. Αν ισχύει στην αρχή ενός γύρου και το values[i] δεν είναι το ζητούμενο, ισχύει και στο τέλος του, με ένα στοιχείο περισσότερο. Όμως ο βρόχος έχει δύο εξόδους: αν εκτελεστεί το return i;, το values[i] είναι το ζητούμενο και, λόγω της αναλλοίωτης, κανένα στοιχείο πριν από αυτό δεν ήταν, οπότε το i είναι η πρώτη εμφάνιση (γι’ αυτό το 112, που εμφανίζεται δύο φορές, αναφέρεται στη θέση 1)· αν ο βρόχος τελειώσει λόγω της συνθήκης, το i ισούται με values.size() και η αναλλοίωτη λέει ότι η τιμή δεν βρίσκεται πουθενά. Το return μέσα στον βρόχο τερματίζει τη συνάρτηση, και μαζί της τον βρόχο, και μας γλιτώνει από μια σημαία.

Το κόστος, με την έννοια του μαθήματος Το κόστος ενός αλγορίθμου, μετριέται με τις συγκρίσεις values[i] == target. Αν η τιμή δεν υπάρχει, γίνονται ακριβώς $n$, μία ανά στοιχείο: η χειρότερη περίπτωση. Αν βρίσκεται στη θέση $p$, γίνονται $p + 1$. Η γραμμική αναζήτηση είναι, επομένως, $O(n)$: με διπλάσια δεδομένα, διπλάσια δουλειά. Χωρίς πρόσθετη πληροφορία δεν γίνεται καλύτερα: ένας αλγόριθμος που θα άφηνε ένα στοιχείο χωρίς να το κοιτάξει δεν θα ήξερε αν η τιμή βρισκόταν εκεί.