lowerBound<T> function

int lowerBound<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 not less than (i.e. greater or equal to) 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 = lowerBound(list, 30); // Returns 2

Implementation

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