Exponential Search
Encontra um valor em um i32[] crescente expandindo o intervalo exponencialmente e depois aplicando busca binária. Retorna o índice zero-based como usize? ou ausência quando o alvo não existe.
tyrus
import { exponentialSearch } from "tyrus:algorithm";
const index: usize? = exponentialSearch([1, 2, 4, 7, 9], 9);
print(index ?? 99); // 4Resultado de estudo
exponentialSearchInfo retorna um ExponentialSearchInfo com as expansões bem-sucedidas e o intervalo final semiaberto pesquisado pela busca binária.
tyrus
interface ExponentialSearchInfo extends SearchInfo {
rangeExpansions: usize;
finalLow: usize;
finalHigh: usize;
}tyrus
import { ExponentialSearchInfo, exponentialSearchInfo } from "tyrus:algorithm";
const info: ExponentialSearchInfo = exponentialSearchInfo([1, 2, 4, 7, 9], 9);
print(info.values); // [1, 2, 4, 7, 9]
print(info.index ?? 99); // 4
print(info.comparisonCount); // 4
print(info.probeCount); // 2
print(info.rangeExpansions); // 2
print(info.finalLow); // 2
print(info.finalHigh); // 5A busca executa em O(log n) e usa espaço auxiliar O(1).
