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;
}