binarySearch<T> function
Returns a position of the value
in sortedList
, if it is there.
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 TypeError
(CastError
on some SDK versions).
Returns -1 if value
is not in the list by default.
Implementation
int binarySearch<T>(List<T> sortedList, T value, {int Function(T, T) compare}) {
compare ??= defaultCompare<T>();
var min = 0;
var max = sortedList.length;
while (min < max) {
var mid = min + ((max - min) >> 1);
var element = sortedList[mid];
var comp = compare(element, value);
if (comp == 0) return mid;
if (comp < 0) {
min = mid + 1;
} else {
max = mid;
}
}
return -1;
}