Interpolation Search

Created on 2023-07-11T08:11:02-05:00

Return to the Index

This card pertains to a resource available on the internet.

This card can also be read via Gemini.

Can perform lookups in O(log log n) time but only if there is a uniform, linear distribution of keys.

Instead of picking the middle point on each split (as in binary search), look at the low and high keys in the range and try to interpolate the position of what you are looking for.