The introspective search iterates between an interpolation search and a binary search.

Any search which would normally run in **O**(ln(ln(*n*))) time when using the
interpolation searching will continue to run in **O**(ln(ln(*n*))) time; while
the worst case for an interpolation search (**O**(*n*)) will instead run in
**O**(ln(*n*)) time.

The basic code alternates between an interpolation search and a binary search recursively.

The enhanced array- and pointer-based implementations use iteration to alternate
between an interpolation search and a binary search until the
array size is less than 500 at which point just binary search is used.