Δυαδική αναζήτηση — ο αριστερότερος δείκτης εισαγωγής

Προϋποθέσεις και στόχος

Ένα τοπικό ευρετήριο αποθηκεύει ταξινομημένους αριθμητικούς κωδικούς. Ζητείται η πρώτη θέση όπου η τιμή δεν είναι μικρότερη από τον κωδικό αναζήτησης. Αν όλες οι τιμές είναι μικρότερες, το αποτέλεσμα είναι το μήκος της λίστας. Με επαναλαμβανόμενες τιμές πρέπει να επιστρέφεται η πρώτη θέση, όχι οποιαδήποτε αντιστοίχιση. Η ταξινόμηση αποτελεί προϋπόθεση: σε αταξινόμητα δεδομένα η διχοτόμηση μπορεί να δώσει λανθασμένο αλλά φαινομενικά λογικό αποτέλεσμα.

Εκτελέσιμο πρόγραμμα Python 3

Αποθήκευσε ως binary_search_lab.py και εκτέλεσε python3 binary_search_lab.py. Η συνάρτηση συγκρίνεται με την bisect_left της τυπικής βιβλιοθήκης για κενές λίστες, διπλότυπα και τιμές έξω από τα όρια.

from bisect import bisect_left

def lower_bound(items, target):
    low, high = 0, len(items)
    while low < high:
        mid = (low + high) // 2
        if items[mid] < target:
            low = mid + 1
        else:
            high = mid
    return low

for row, targets in [
    ([], [-1, 0]),
    ([1,1,2,4], [0,1,2,3,4,5]),
    ([-5,0,0,8], [-8,-5,0,1,9])
]:
    for target in targets:
        index = lower_bound(row, target)
        assert index == bisect_left(row, target)
        assert all(value < target for value in row[:index])
        assert all(value >= target for value in row[index:])
print("PASS: leftmost insertion, duplicates, empty and boundaries")

Απόδειξη ορθότητας

Σε κάθε επανάληψη το διάστημα [low, high) περιέχει τον πρώτο επιτρεπτό δείκτη εισαγωγής. Όσα στοιχεία προηγούνται του low είναι μικρότερα από τον στόχο, ενώ όσα βρίσκονται από το high και μετά είναι μεγαλύτερα ή ίσα. Αν το μεσαίο στοιχείο είναι μικρότερο, μετακινούμε το low στο mid+1. Διαφορετικά, η σωστή θέση βρίσκεται στο mid ή αριστερότερα και μεταφέρουμε το high στο mid. Το διάστημα μικραίνει αυστηρά μέχρι οι δύο δείκτες να συμπέσουν. Για n ταξινομημένα στοιχεία απαιτούνται O(log n) συγκρίσεις και O(1) βοηθητική μνήμη.

Ασκήσεις με σαφή αναμενόμενα αποτελέσματα

1. Άλλαξε τη σύγκριση σε μικρότερο-ή-ίσο και παρατήρησε πώς τα διπλότυπα οδηγούν στη δεξιά θέση εισαγωγής.
2. Δοκίμασε κενή λίστα, μία τιμή, ίδιες τιμές, αρνητικά και απούσα τιμή. Πρόβλεψε πρώτα κάθε δείκτη.
3. Εφάρμοσε τη συνάρτηση σε αταξινόμητη λίστα και κατέγραψε την παραβίαση του συμβολαίου. Αποφάσισε αν θα γίνεται ταξινόμηση από τον καλούντα ή απόρριψη.
4. Γράψε παραλλαγή που επιστρέφει δείκτη υπαρκτής τιμής ή None. Εξήγησε γιατί η αρχική λύση βοηθά και σε αναζητήσεις διαστήματος.

Παραδοτέα: PASS, περιγραφή του αμετάβλητου διαστήματος και τουλάχιστον δέκα οριακές συγκρίσεις.