lowerBound<E, V> function

int lowerBound<E, V>(
  1. List<E> list,
  2. V value, {
  3. int? start,
  4. int? count,
  5. EntryComparator<E, V>? compare,
})

Returns the index of the first item from a sorted list that is either equal to or greater than the the value, otherwise if all items are lesser than the value, the length of the list is returned.

Parameters

  • The list must be a sorted list of items, otherwise the behavior of this method is not defined.
  • The value must be comparable with the items on the list. Otherwise, TypeError is thrown.
  • If start is given, search start there and go towards the end of the list.
  • If start is negative, search starts at start + count or 0, whichever is greater.
  • If start is not below the length of the list, the length is returned.
  • If the count parameter is given, it will check up to count numbers of items.
  • The count must not be negative. Otherwise, RangeError is thrown.
  • compare is a custom compare function between a list element and the value. If it is null, compareTo method of list item is used.

Details

The search will begin with a range from start and consider at most count number of items. In each iteration, the range will be narrowed down by half. If the middle item of the range is less than the value, the right half of the range will be selected, otherwise the left half. After this process is done, we are left with a singular range containing only one item.

Complexity: Time O(log n) | Space O(1)

Implementation

int lowerBound<E, V>(
  List<E> list,
  V value, {
  int? start,
  int? count,
  EntryComparator<E, V>? compare,
}) {
  int b, e;
  int n = list.length;

  // determine range [i, j)
  b = start ?? 0;
  e = n;
  if (count != null) {
    if (count < 0) {
      throw RangeError("count can not be negative");
    }
    e = b + count;
    if (e > n) e = n;
  }
  if (b < 0) b = 0;

  if (compare == null) {
    return lowerBoundDefault<E, V>(list, value, b, e);
  } else {
    return lowerBoundCustom<E, V>(list, value, b, e, compare);
  }
}