BinarySearch

BinarySearch

pub fn BinarySearch<T>(Values: readonly T[], Key: readonly T&,
    Compare: fn(readonly T&, readonly T&) -> i32) -> Result<usize, usize>

Finds the first equal element or its lower-bound insertion position.

Performs O(log n) safe borrowed comparisons and uses O(1) state. No element copies/moves, allocation, mutation or synchronization occurs. Values must already be sorted by the same consistent ordering; the key remains borrowed through this synchronous call. Duplicate matches choose their first index. T: Exact stored element type, including non-Copy owning values. Values: Sorted readonly contiguous storage; backing stays live and unchanged. Key: Borrowed comparison target; not retained by the result. Compare: Safe negative/zero/positive borrowed ordering callback. Return: Ok containing the first equal index, or Err containing an insertion index in [0,Length]. Pre: Compare provides the ordering used to sort Values and never invalidates its backing. Warning: Incorrect ordering violates the search precondition; no linear validation pass is added.

Example

module example.binary_search;
from std.iteration import BinarySearch;
fn Compare(Left: i32&, Right: i32&) -> i32 {
    if Left < Right { return -1; }
    if Left > Right { return 1; }
    return 0;
}
fn Main() -> i32 {
    let Values: i32[4] = [10, 20, 20, 42];
    switch BinarySearch<i32>(Values, 20, Compare) {
        case .Ok { Value = Index } => { if Index != 1 { return 1; } }
        case .Err { Error = _ } => return 2;
    }
    switch BinarySearch<i32>(Values, 21, Compare) {
        case .Err { Error = Position } => { if Position != 3 { return 3; } }
        case .Ok { Value = _ } => return 4;
    }
    let Empty: i32[0] = [];
    switch BinarySearch<i32>(Empty, 42, Compare) {
        case .Err { Error = Position } => { if Position != 0 { return 5; } }
        case .Ok { Value = _ } => return 6;
    }
    return 0;
}