Οδηγός Μελέτης - Εισαγωγή στον Προγραμματισμό

Κ17.6 · Βήματα δυαδικής αναζήτησης σε 2^50 στοιχεία

Kahoot «Δυαδική Αναζήτηση και Ταξινόμηση» (διάλεξη 17) και «Δυαδική Αναζήτηση, Ταξινόμηση, Πολυπλοκότητα και άλλα» · Δυσκολία ★★☆ · multiple-choice · 52% σωστές απαντήσεις (101 απαντήσεις στο αμφιθέατρο) · Κεφάλαια: 17

Αναζητώ έναν ακέραιο σε ταξινομημένο πίνακα με \(10^{15} \approx 2^{50}\) στοιχεία. Με δυαδική αναζήτηση θα χρειαστώ τόσα βήματα:

• \[10^{15}\]
• \[10^{7.5}\]
• \[2^{10}\]
• 50

Υπόδειξη

Κάθε βήμα της δυαδικής αναζήτησης υποδιπλασιάζει το διάστημα που απομένει· πόσες φορές πρέπει να διαιρέσετε το \(2^{50}\) με το 2 για να φτάσετε στο 1;

Αριθμός στον οδηγό: Κ17.6 (στο κεφάλαιο) · Μόνιμο αναγνωριστικό: kahoot-binary-search-steps · Σύνδεσμος: https://progintro.github.io/study/questions/kahoot/kahoot-binary-search-steps.html · Markdown (GitHub)