binarySearch

Returns the index of an element in items returning .eq when given to compareFn.

If there are multiple such elements, returns the index of any one of them.
If there are no such elements, returns null.

items must be sorted in ascending order with respect to compareFn:

[0]                                                   [len]
┌───┬───┬─/ /─┬───┬───┬───┬─/ /─┬───┬───┬───┬─/ /─┬───┐
│.lt│.lt│ \ \ │.lt│.eq│.eq│ \ \ │.eq│.gt│.gt│ \ \ │.gt│
└───┴───┴─/ /─┴───┴───┴───┴─/ /─┴───┴───┴───┴─/ /─┴───┘
├─────────────────┼─────────────────┼─────────────────┤
 ↳ zero or more    ↳ zero or more    ↳ zero or more
                  ├─────────────────┤
                   ↳ if not null, returned
                     index is in this range

O(log n) time complexity.

See also: lowerBound, upperBound, partitionPoint, equalRange.

Function parameters

Parameters

T:type
items:[]const T
context:anytype
compareFn:fn (@TypeOf(context), T) std.math.Order

Type definitions in this namespace

Types

Mode

Functions in this namespace

Functions

block
pdq
pdqContext
insertion: Stable in-place sort.
insertionContext: Stable in-place sort.
heap: Unstable in-place sort.
heapContext: Unstable in-place sort.
asc: Use to generate a comparator function for a given type.
desc: Use to generate a comparator function for a given type.
binarySearch: Returns the index of an element in `items` returning `.eq` when given to `compareFn`.
lowerBound: Returns the index of the first element in `items` that is greater than or equal to `context`,
upperBound: Returns the index of the first element in `items` that is greater than `context`, as determined
partitionPoint: Returns the index of the partition point of `items` in relation to the given predicate.
equalRange: Returns a tuple of the lower and upper indices in `items` between which all
argMin
min
argMax
max
isSorted

Source

Implementation

pub fn binarySearch(
    comptime T: type,
    items: []const T,
    context: anytype,
    comptime compareFn: fn (@TypeOf(context), T) std.math.Order,
) ?usize {
    var low: usize = 0;
    var high: usize = items.len;

    while (low < high) {
        // Avoid overflowing in the midpoint calculation
        const mid = low + (high - low) / 2;
        switch (compareFn(context, items[mid])) {
            .eq => return mid,
            .gt => low = mid + 1,
            .lt => high = mid,
        }
    }
    return null;
}