Interpolation Search
Busca un i32[] ascendente estimando la posición del objetivo a partir de los valores en los límites actuales. Devuelve un usize? zero-based, o ausencia cuando falta el objetivo. El array debe estar ordenado de forma ascendente.
tyrus
import { interpolationSearch } from "tyrus:algorithm";
const index: usize? = interpolationSearch([1, 2, 4, 7, 9], 4);
print(index ?? 99); // 2Resultado de estudio
interpolationSearchInfo devuelve un InterpolationSearchInfo, incluida cada posición estimada usada por la búsqueda.
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]La complejidad media es O(log log n) para valores uniformemente distribuidos, con O(n) en el peor caso y espacio auxiliar O(1).
