lowerBound

Returns the index of the first element in items that is greater than or equal to context, as determined by compareFn. If no such element exists, returns items.len.

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
                  ├───┤
                   ↳ returned index

O(log n) time complexity.

See also: binarySearch, 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 lowerBound(
    comptime T: type,
    items: []const T,
    context: anytype,
    comptime compareFn: fn (@TypeOf(context), T) std.math.Order,
) usize {
    const S = struct {
        fn predicate(ctx: @TypeOf(context), item: T) bool {
            return compareFn(ctx, item).invert() == .lt;
        }
    };
    return partitionPoint(T, items, context, S.predicate);
}