Function std.range.SortedRange.equalRange
Returns the subrange containing all elements e
for which both pred(e, value)
and pred(value, e)
evaluate to false
(e.g.,
if pred
is "less than", returns the portion of the range with
elements equal to value
). Uses a classic binary search with
interval halving until it finds a value that satisfies the condition,
then uses SearchPolicy
to find the left boundary
and SearchPolicy
to find the right boundary. These
policies are justified by the fact that the two boundaries are likely
to be near the first found value (i.e., equal ranges are relatively
small). Completes the entire search in Ο(log(n)
) time.
auto auto equalRange(V)
(
V value
)
if (isTwoWayCompatible!(predFun, ElementType!Range, V) && isRandomAccessRange!Range);
Example
import std .algorithm .comparison : equal;
auto a = [ 1, 2, 3, 3, 3, 4, 4, 5, 6 ];
auto r = a .assumeSorted .equalRange(3);
assert(equal(r, [ 3, 3, 3 ]));
Authors
Andrei Alexandrescu, David Simcha, Jonathan M Davis, and Jack Stouffer. Credit for some of the ideas in building this module goes to Leonardo Maffi.