lowerBound< T> function
Returns the first position in sortedList
that does not compare less than
value
.
If the list isn't sorted according to the compare
function, the result
is unpredictable.
If compare
is omitted, this defaults to calling Comparable.compareTo on
the objects. If any object is not Comparable, this throws a CastError.
Returns sortedList.length
if all the items in sortedList
compare less
than value
.
Implementation
int lowerBound<T>(List<T> sortedList, T value, {int compare(T a, T b)}) {
compare ??= defaultCompare<T>();
int min = 0;
int max = sortedList.length;
while (min < max) {
int mid = min + ((max - min) >> 1);
var element = sortedList[mid];
int comp = compare(element, value);
if (comp < 0) {
min = mid + 1;
} else {
max = mid;
}
}
return min;
}