binarySearch<E, V> function

int binarySearch<E, V>(
  1. List<E> list,
  2. V value, {
  3. int? start,
  4. int? count,
  5. EntryComparator<E, V>? compare,
})

Returns the index of the first occurance of the value in a sorted list, otherwise -1 if not found. It is ensured that the index is as lowest as possible.

Parameters

  • The list must be a sorted list of items, otherwise the behavior of this method is not defined.
  • The value must be comparable with the list items. Otherwise, TypeError is thrown.
  • If start is given, search start there and go towards the end of the list.
  • If start is not below the length of the list, -1 is returned.
  • If start is negative, search starts at start + count or 0, whichever is greater.
  • If the count parameter is given, it will check up to count numbers of items.
  • If count is negative, -1 is returned.
  • compare is a custom compare function between a list element and the value. If it is null, compareTo method of list item is used.

Details

The search will begin with a range from start and consider at most count number of items. In each iteration, the range will be narrowed down by half. If the middle item of the range is less than the value, the right half of the range will be selected, otherwise the left half. After this process is done, we are left with a singular range containing only one item.

If this item is equal to the value, the index is returneds, otherwise -1.

Complexity: Time O(log n) | Space O(1)

Implementation

int binarySearch<E, V>(
  List<E> list,
  V value, {
  int? start,
  int? count,
  EntryComparator<E, V>? compare,
}) {
  int b, e, l;
  int n = list.length;

  // determine range [i, j)
  b = start ?? 0;
  e = n;
  if (count != null) {
    if (count < 0) return -1;
    e = b + count;
    if (e > n) e = n;
  }
  if (b < 0) b = 0;

  if (compare == null) {
    l = lowerBoundDefault<E, V>(list, value, b, e);
  } else {
    l = lowerBoundCustom<E, V>(list, value, b, e, compare);
  }

  // binary search result
  if (b <= l && l < e) {
    if (compare == null) {
      if (list[l] == value) return l;
    } else {
      if (compare(list[l], value) == 0) return l;
    }
  }
  return -1;
}