jumpSearch static method

int jumpSearch({ required List<String> list, required String target, bool isSorted = false, })

Jump search: searches the list by jumping ahead by a fixed step size.

The list must be sorted. If not sorted, set isSorted to false and it will sort the list first.

Returns the index of the target element if found, otherwise -1.

Implementation

static int jumpSearch({
  required List<String> list,
  required String target,
  bool isSorted = false, // Default value set to false
}) {
  if (!isSorted) {
    list = List<String>.from(list)
        .quickSort(); // Sort the list if not already sorted
  }

  int n = list.length;
  int step = sqrt(n).toInt(); // Block size to be jumped
  int prev = 0;

  // Jump through the list until we find a block where the target might be
  while (list[min(step, n) - 1].compareTo(target) < 0) {
    prev = step;
    step += sqrt(n).toInt();
    if (prev >= n) {
      return -1; // Element not found, return -1
    }
  }

  // Linear search within the identified block
  for (int i = prev; i < min(step, n); i++) {
    if (list[i] == target) {
      return i; // Element found, return its index
    }
  }

  return -1; // Element not found, return -1
}