partitionPoint

Returns the index of the partition point of items in relation to the given predicate.

If all elements of items satisfy the predicate the returned value is items.len.

items must contain a prefix for which all elements satisfy the predicate, and beyond which none of the elements satisfy the predicate:

[0]                                          [len]
┌────┬────┬─/ /─┬────┬─────┬─────┬─/ /─┬─────┐
│true│true│ \ \ │true│false│false│ \ \ │false│
└────┴────┴─/ /─┴────┴─────┴─────┴─/ /─┴─────┘
├────────────────────┼───────────────────────┤
 ↳ zero or more       ↳ zero or more
                     ├─────┤
                      ↳ returned index

O(log n) time complexity.

See also: binarySearch, lowerBound, upperBound, equalRange.

Function parameters

Parameters

T:type
items:[]const T
context:anytype
predicate:fn (@TypeOf(context), T) bool

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 partitionPoint(
    comptime T: type,
    items: []const T,
    context: anytype,
    comptime predicate: fn (@TypeOf(context), T) bool,
) usize {
    var low: usize = 0;
    var high: usize = items.len;

    while (low < high) {
        const mid = low + (high - low) / 2;
        if (predicate(context, items[mid])) {
            low = mid + 1;
        } else {
            high = mid;
        }
    }
    return low;
}