Interpolation Search
Busca um i32[] crescente estimando a posição do alvo a partir dos valores nos limites atuais. Retorna um usize? zero-based ou ausência quando o alvo não existe. O array deve estar ordenado em ordem crescente.
tyrus
import { interpolationSearch } from "tyrus:algorithm";
const index: usize? = interpolationSearch([1, 2, 4, 7, 9], 4);
print(index ?? 99); // 2Resultado de estudo
interpolationSearchInfo retorna um InterpolationSearchInfo, incluindo cada posição estimada usada pela busca.
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]A complexidade média é O(log log n) para valores uniformemente distribuídos, com O(n) no pior caso e espaço auxiliar O(1).
