Animation: Interpolation Search

Animation Systems Collection--Animations Collection

Description

Interpolation search is an extension of the binary search. Like the binary search the goal of the Interpolation search is to find a certain element. In analogy to the binary search the Interpolation search requires that the elements are sorted in ascending order.

The basic idea is similar to leafing through the telephone book where one Does not just chose the middle element of the search area but decides where it is most likely to be judging by the range limits.

To that end the difference of the first element of the interval (the smallest element) to the element to be searched is divided by the span of the interval values in relation to the interval length. Multiplied with the interval boundaries that then is the interpolated position of the element to be searched.

With approximately evenly distributed values, the expected complexity of the Interpolation Search is ca. O(log log n)

The animation demonstrates the course of a failed Interpolation search and shows the source code. To better understand the procedure, the current code line is highlighted.

Screen Shot(s):

Initial state

Determining the first comparison position

Not found - continue in right subarray

Element found after two steps

Classification

• Algorithms
• Searching Algorithms

Animation Rating

You can provide a rating for this animation. The rating is performed on a scale of 1 to 10, where 10 is the highest possible grade.

1(very bad) 2 3 4 5 6 7 8 9 10(very good)

File information

Title	Interpolation Search
Animation URL	http://www.animal.ahrgr.de/Anims/en/interpolationSearch2.aml
Animation Applet	Animal Applet
Animation System	Animal
Animation Type	dynamic full VCR
Supported OS(s)	Linux,MacOS,Windows 95,Windows 98,Windows ME,Windows NT,Windows 2000,Unix
Author(s)	Carsten Schwender
Date	1999-05-10
File Size size	3263 Byte
Number of Accesses:	8474
Added to DB by	Guido Rößling
Average Rating	5.9333(30 submitted ratings)
Language:	en
Number of Accesses:	8474

BibTeX bibliographic entry for citations:

@Misc{Schwender:1999,
   author = {Carsten Schwender},
   title = {Interpolation Search},
   howpublished = {WWW: \url{http://www.animal.ahrgr.de/Anims/en/interpolationSearch2.aml}},
 }