bisect_left<E> function
int
bisect_left<E>(
- List<
E> a, - E x, {
- int lo = 0,
- int? hi,
- ToKey<
E, Object> ? key, - Comparator<
E> ? compare,
Locate the insertion point for x in a to maintain sorted order. The parameters 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 a
, the insertion point will be before (to the
left of) any existing entries. The return value is suitable for use as the first parameter
to List.insert
assuming that a is already sorted.
Implementation
int bisect_left<E>(List<E> a, E x,
{int lo = 0, int? hi, ToKey<E, Object>? key, Comparator<E>? compare}) {
compare = argToComparator<E>(compare, key);
if (lo < 0) {
throw ArgumentError.value(
lo, 'lo must be non-negative'); // in Python this disallowed too
}
if (hi != null && hi < 0) {
// Python allows negative `hi` values, but returns strange results.
// I failed to make a Dart code that returns the same, in particular in the case of `hi=-1`.
// But negative `hi` does not make sense. So we'll just disallow it
throw ArgumentError.value(lo, 'hi must be non-negative');
}
int h = hi ?? a.length;
while (lo < h) {
int mid = (lo + h) >> 1; // in Python it's `//2`
if (compare(a[mid], x) < 0) {
lo = mid + 1;
} else {
h = mid;
}
}
return lo;
}