Binary Interpolation Searching

[Re4cTiV3]

Καλησπέρα..υπάρχει αλγόριθμος για binary interpolation searching δηλαδή όλα σε ένα;

 

Κάπου είδα ότι η βελτίωση της χειρότερης περίπτωσης του Interpolation Searching γίνεται με την Binary Interpolation Searching αλλά δεν βρήκα κάπου κάποιον αλγόριθμο.Ξέρετε τίποτα;

[defacer]

Αυτό που ψάχνεις λέγεται απλώς binary search. Πρόκειται για την υποπερίπτωση του interpolation searching όπου πάντα επιλέγεις το μέσο του διαστήματος στο οποίο ψάχνεις για έλεγχο ισότητας. Τα μεγάλα της πλεονεκτήματα είναι η εγγύηση O(logn) και το ότι δε χρειάζεται να ξέρεις απολύτως τίποτα για την κατανομή των αντικειμένων στα οποία ψάχνεις.

[Re4cTiV3]

Διαβάζω τώρα στο βιβλίο Δομές Δεδομένων του Τσακαλίδη αυτό εδώ και με μπέρδεψες :/

 

http://imgur.com/xRu3U