equalRange

Returns a tuple of the lower and upper indices in items between which all elements return .eq when given to compareFn.

If no element in items returns .eq, both indices are the index of the first element in items returning .gt.
If no element in items returns .gt, both indices equal 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 range

O(log n) time complexity.

See also: binarySearch, lowerBound, upperBound, partitionPoint.

Source

Implementation

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

    while (low < high) {
        const mid = low + (high - low) / 2;
        switch (compareFn(context, items[mid])) {
            .gt => {
                low = mid + 1;
            },
            .lt => {
                high = mid;
            },
            .eq => {
                return .{
                    low + std.sort.lowerBound(
                        T,
                        items[low..mid],
                        context,
                        compareFn,
                    ),
                    mid + std.sort.upperBound(
                        T,
                        items[mid..high],
                        context,
                        compareFn,
                    ),
                };
            },
        }
    }

    return .{ low, low };
}