Interpolation search is an algorithm for searching for a key in an array that has been ordered by the numerical values assigned to its keys. Unlike binary search, which always probes the middle element of the remaining range, interpolation search estimates the probable position of the key using linear interpolation between the values at the ends of the range, giving an average time of O(log log n) on uniformly distributed data, though its worst case remains O(n). It was first described by W. W. Peterson in 1957. This description is adapted from Wikipedia contributors under CC BY-SA 4.0; changes were made. https://creativecommons.org/licenses/by-sa/4.0/
Facts
Time Complexity
Time Complexity (category) Time Complexity (category) Time ComplexityWorst-case O(n), best-case O(1), average O(log log n) for uniformly distributed data. 1 Connections
In Field
Source Wikipedia: Interpolation Search
Sources
1. Wikipedia: Interpolation Search
Wikimedia FoundationLead section
It was first described by W. W. Peterson in 1957.
In Field: Algorithms and Complexity Theory, Lead sentence
Interpolation search is an algorithm for searching for a key in an array that has been ordered by numerical values assigned to the keys (key values).
View the Source Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.