An approximate location is interpolated from the first and last items of a sorted array, then a linear search finds the actual location.