Interpolation Search
Searches an ascending i32[] by estimating the target position from the values at the current bounds. It returns a zero-based usize?, or absence when the target is missing. The array must be sorted in ascending order.
tyrus
import { interpolationSearch } from "tyrus:algorithm";
const index: usize? = interpolationSearch([1, 2, 4, 7, 9], 4);
print(index ?? 99); // 2Study result
interpolationSearchInfo returns an InterpolationSearchInfo, including every estimated position used by the search.
tyrus
interface InterpolationSearchInfo extends SearchInfo {
estimatedPositions: usize[];
}tyrus
import { InterpolationSearchInfo, interpolationSearchInfo } from "tyrus:algorithm";
const info: InterpolationSearchInfo = interpolationSearchInfo([1, 2, 4, 7, 9], 4);
print(info.values); // [1, 2, 4, 7, 9]
print(info.index ?? 99); // 2
print(info.comparisonCount); // 2
print(info.probeCount); // 2
print(info.estimatedPositions); // [1, 2]The average complexity is O(log log n) for uniformly distributed values, with O(n) worst-case complexity and O(1) auxiliary space.
