upperBound<E, V> function

int upperBound<E, V>(
  1. List<E> list,
  2. V value, {
  3. int? start,
  4. int? count,
  5. EntryComparator<E, V>? compare,
  6. bool exactMatch = false,
})

Returns the index of the first item from a sorted list that is strictly greater than the value, otherwise if all items are less than or equal to 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 not below the length of the list, the length is returned.
  • If start is negative, search starts at start + count or 0, whichever is greater.
  • 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.
  • To use custom comparison between the list items and the value, pass the compare function.

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 or equal to the value, 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 upperBound<E, V>(
  List<E> list,
  V value, {
  int? start,
  int? count,
  EntryComparator<E, V>? compare,
  bool exactMatch = false,
}) {
  int b, e;
  int n = list.length;

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

  if (compare == null) {
    return upperBoundDefault(list, value, b, e);
  } else {
    return upperBoundCustom(list, value, b, e, compare);
  }
}