Exponential Search
Finds a value in an ascending i32[] by expanding the search range exponentially and then applying binary search. It returns the zero-based index as usize?, or absence when the target is missing.
tyrus
import { exponentialSearch } from "tyrus:algorithm";
const index: usize? = exponentialSearch([1, 2, 4, 7, 9], 9);
print(index ?? 99); // 4Study result
exponentialSearchInfo returns an ExponentialSearchInfo with the successful range expansions and the final half-open range searched by binary search.
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); // 5The search runs in O(log n) time and uses O(1) auxiliary space.
