binarySearchUpper<E, V> function

int binarySearchUpper<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 last occurance of the value in a sorted list, otherwise -1 if not found.

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 list items. 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, -1 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.
  • If count is negative, -1 is returned.
  • 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 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.

If the item is equal to value, the index will be returned, otherwise -1.

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

Implementation

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

  // determine range [i, j)
  b = start ?? 0;
  e = n;
  if (count != null) {
    if (count < 0) return -1;
    e = b + count;
    if (e > n) e = n;
  }
  if (b < 0) b = 0;

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

  // binary search result
  u--;
  if (b <= u) {
    if (compare == null) {
      if (list[u] == value) return u;
    } else {
      if (compare(list[u], value) == 0) return u;
    }
  }
  return -1;
}