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 CastError.
Returns -1 if value
is not in the list by default.
Implementation
int binarySearch<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) return mid;
if (comp < 0) {
min = mid + 1;
} else {
max = mid;
}
}
return -1;
}