Αναζήτηση παρεμβολής
- Στη αναζήτηση παρεμβολής (interpolation search) η εύρεση
της εγγραφής στον (ταξινομημένο) πίνακα γίνεται υπολογίζοντας την
πιθανή θέση της εγγραφής σε σχέση με τις τιμές των στοιχείων στα άκρα
της περιοχής αναζήτησης.
Ανάλογα με τη σύγκριση της τιμής της εγραφής με την εγγραφή στην
πιθανή θέση αναπροσαρμόζεται το αντίστοιχο άκρο.
- Αν ο πίνακας έχει στοιχεία ομοιόμορφα κατανεμημένα θα απαιτηθούν
O(log log n) συγκρίσεις.