upperBound<T> function

int upperBound<T>(
  1. List<T> list,
  2. T value, {
  3. int compare(
    1. T,
    2. T
    )?,
})

Returns the index of the first element in the list that is strictly greater than value.

The list must be partitioned with respect to value (e.g., sorted). Performs $O(\log N)$ comparisons via binary search.

Optionally takes a custom compare function to define the ordering.

Example:

final list = [10, 20, 30, 30, 40, 50];
final index = upperBound(list, 30); // Returns 4

Implementation

int upperBound<T>(List<T> list, T value, {int Function(T, T)? compare}) {
  compare ??= _defaultCompare;
  var min = 0;
  var max = list.length;
  while (min < max) {
    var mid = min + ((max - min) >> 1);
    var element = list[mid];
    var comp = compare(element, value);
    if (comp <= 0) {
      min = mid + 1;
    } else {
      max = mid;
    }
  }
  return min;
}