binarySearch<T> function

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

Checks if an element equivalent to value appears within the list.

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. Returns true if found, false otherwise.

Example:

final list = [10, 20, 30, 30, 40, 50];
final found = binarySearch(list, 30); // Returns true

Implementation

bool binarySearch<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) return true;
    if (comp < 0) {
      min = mid + 1;
    } else {
      max = mid;
    }
  }
  return false;
}