tag

#interpolation-search

2 pages tagged

Wiki › Algorithms › 01. Searching and Sorting › 2. Binary Search and Ordered Search ›

Interpolation Search

Interpolation Search Interpolation search is a search algorithm for sorted numeric arrays. Like binary search, it repeatedly narrows the search interval. Unlike binary search, it does not always choose the middle position. It estimates where the target should be based on the values at the ends of the interval. This works well when values are close to uniformly distributed. For example, if the target is near the value at the...

Wiki › Algorithms › 01. Searching and Sorting › 12. Specialized Search and Sorted-Order Procedures ›

Interpolation Search with Fallback

Interpolation Search with Fallback Interpolation search with fallback combines the speed of interpolation search on well distributed numeric keys with the reliability of binary search. It estimates where the target should be by value, but falls back to ordinary binary search when the estimate becomes poor, unstable, or unsafe. This gives good performance on near uniform data while preserving the worst case behavior of binary search. Problem Given a sorted...