A distribution search requires that there is a best-fitting line which passes through the data together with a maximum error: array[i] = a*i + b ± B₁ for real values of a, b, and M. In this case, it is possible to find an inverse function floor( (array[i] - b - M)/a ), ..., ceil( (array[i] - b + M)/a ) which maps a value onto a possible range of values. At this point, based on the width 2M/a, either introspective, binary, or linear search may now be used.

The run time of this algorithm is O( M/a ln(M/a) ).