bisectLeft<T> function
Bisecting data
Returns the insertion point for x
in list
to maintain sorted order
according to the specified comparator
.
The arguments lo
and hi
may be used to specify a subset of the list
which should be considered; by default the entire list is used. If x
is
already present in list
, the insertion point will be before (to the left
of) any existing entries. The return value is suitable for use as the first
argument to List.insert assuming that list
is already sorted. The
returned insertion point i partitions the list
into two halves so that
all v < x
for v in list
.sublist(lo
, i) for the left side and all
v >= x
for v in list
.sublist(i, hi
) for the right side.
Implementation
int bisectLeft<T>(List<T> list, T x,
{int lo = 0, int? hi, num Function(T, T) comparator = ascending}) {
hi ??= list.length;
if (lo < hi) {
if (comparator(x, x) != 0) return hi;
do {
var mid = (lo + hi!) >>> 1;
if (comparator(list[mid], x) < 0) {
lo = mid + 1;
} else {
hi = mid;
}
} while (lo < hi);
}
return lo;
}