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.