interpolationSearch<T>

A generic implementation of the Interpolation Search algorithm that efficiently finds a target element in a sorted list by estimating its position.

Function Signature

int interpolationSearch<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 target is found at the estimated position
• Average Case: O(log log n) - When data is uniformly distributed
• Worst Case: O(n) - When data is not uniformly distributed

Space Complexity

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

Implementation

int interpolationSearch<T extends Comparable<T>>(List<T> list, T target) {
  var low = 0;
  var high = list.length - 1;

  while (low <= high && 
         target.compareTo(list[low]) >= 0 && 
         target.compareTo(list[high]) <= 0) {
    
    if (low == high) {
      if (list[low].compareTo(target) == 0) return low;
      return -1;
    }

    // Calculate probe position
    var position = low + ((high - low) * 
      (target.compareTo(list[low])) ~/ 
      (list[high].compareTo(list[low])));

    // Target found
    if (list[position].compareTo(target) == 0) {
      return position;
    }

    // If target is larger, target is in upper part
    if (list[position].compareTo(target) < 0) {
      low = position + 1;
    } else {
      // If target is smaller, target is in lower part
      high = position - 1;
    }
  }
  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 probe position using interpolation formula
   • Compares the element at probe position with target
   • Adjusts search range based on comparison
   • Continues until element is found or range is invalid

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 = interpolationSearch(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 = interpolationSearch(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:

   • Most efficient for uniformly distributed data
   • Can outperform binary search for uniform distributions
   • May degrade to linear search for non-uniform distributions

3. Best Use Cases:

   • Large sorted arrays with uniform distribution
   • When data values are evenly distributed
   • When faster than binary search performance is needed