Exponential Search
Encuentra un valor en un i32[] ascendente expandiendo el intervalo exponencialmente y aplicando después búsqueda binaria. Devuelve el índice zero-based como usize?, o ausencia cuando falta el objetivo.
tyrus
import { exponentialSearch } from "tyrus:algorithm";
const index: usize? = exponentialSearch([1, 2, 4, 7, 9], 9);
print(index ?? 99); // 4Resultado de estudio
exponentialSearchInfo devuelve un ExponentialSearchInfo con las expansiones correctas y el intervalo semiabierto final buscado por la búsqueda binaria.
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); // 5La búsqueda se ejecuta en O(log n) y usa espacio auxiliar O(1).
