jumpSearch<T>

A generic implementation of the Jump Search algorithm that searches for a target element in a sorted list by jumping fixed steps.

Function Signature

int jumpSearch<T extends Comparable<T>>(List<T> list, T target)

Parameters

• list: A sorted list of elements of type T that implements the Comparable interface
• target: The element to search for in the list

Return Value

• Returns the index of the target element if found
• Returns -1 if the target element is not found in the list

Type Parameters

• T extends Comparable<T>: The type parameter T must implement the Comparable interface to ensure elements can be compared

Complexity Analysis

Time Complexity

• Best Case: O(1) - When the first element is the target
• Average Case: O(√n)
• Worst Case: O(√n) - When the target is near the end or not present

Space Complexity

• O(1) - Only requires a constant amount of extra space

Implementation

int jumpSearch<T extends Comparable<T>>(List<T> list, T target) {
  final n = list.length;
  if (n == 0) return -1;

  // Finding the optimal jump step size
  final step = sqrt(n).floor();
  
  // Finding the block where element is present (if it exists)
  var prev = 0;
  var jump = step;
  
  // Finding the block
  while (jump < n && list[jump].compareTo(target) < 0) {
    prev = jump;
    jump += step;
  }
  
  // Linear search within the identified block
  while (prev <= min(jump, n - 1)) {
    if (list[prev].compareTo(target) == 0) {
      return prev;
    }
    prev++;
  }
  
  return -1;
}

Implementation Details

1. Function Declaration:

   • The function is generic, accepting any type T that implements Comparable<T>
   • Takes two parameters: the sorted list and the target element
   • Returns an integer representing the index of the target element

2. Algorithm Steps:

   • Calculates the optimal jump step size (√n)
   • Jumps through blocks until finding a block that may contain the target
   • Performs linear search within the identified block
   • Returns the index if found, -1 otherwise

Example Usage

void main() {
  // Searching in a list of integers
  var numbers = [11, 12, 22, 25, 34, 64, 90];
  var target = 34;
  print('List: $numbers');
  var index = jumpSearch(numbers, target);
  print('Index of $target: $index');

  // Searching in a list of strings
  var fruits = ['apple', 'banana', 'grape', 'orange'];
  var searchFruit = 'grape';
  print('\nList: $fruits');
  var fruitIndex = jumpSearch(fruits, searchFruit);
  print('Index of $searchFruit: $fruitIndex');
}

Output

List: [11, 12, 22, 25, 34, 64, 90]
Index of 34: 4

List: [apple, banana, grape, orange]
Index of grape: 2

Usage Notes

1. Prerequisites:

   • The input list MUST be sorted in ascending order
   • The type T must implement Comparable<T>
   • Built-in types like int, double, and String already implement Comparable

2. Performance Considerations:

   • More efficient than linear search for sorted arrays
   • Less efficient than binary search but requires fewer comparisons
   • Optimal for searching in arrays stored in external memory or on disk

3. Best Use Cases:

   • Medium-sized sorted arrays
   • When binary search is too complex to implement
   • When data is stored in external memory