binarySearchByKey<K extends Comparable> method

Result<int, int> binarySearchByKey<K extends Comparable>(
  1. K key,
  2. K keyExtractor(
    1. T
    )
)

Binary searches this slice with a key extraction function. See SliceOnComparableSliceExtension.binarySearch for more.

Implementation

Result<int, int> binarySearchByKey<K extends Comparable>(
    K key, K Function(T) keyExtractor) {
  int left = 0;
  int right = length - 1;

  while (left <= right) {
    int mid = left + ((right - left) >> 1);
    K midKey = keyExtractor(getUnchecked(mid));
    int comp = midKey.compareTo(key);

    if (comp == 0) {
      return Ok(mid);
    } else if (comp < 0) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  // If not found, return the index where it can be inserted to maintain sorted order.
  return Err(left);
}