linearSearch<T>

A generic implementation of the Linear Search algorithm that sequentially searches for a target element in a list.

Function Signature

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

Parameters

• list: A 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 at the first position
• Average Case: O(n)
• Worst Case: O(n) - When the target is at the last position or not present

Space Complexity

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

Implementation

int linearSearch<T extends Comparable<T>>(List<T> list, T target) {
  for (var i = 0; i < list.length; i++) {
    if (list[i].compareTo(target) == 0) {
      return i;
    }
  }
  return -1;
}

Implementation Details

1. Function Declaration:

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

2. Algorithm Steps:

   • Iterates through each element in the list sequentially
   • Compares each element with the target
   • Returns the index when a match is found
   • Returns -1 if no match is found after checking all elements

Example Usage

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

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

Output

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

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

Usage Notes

1. Advantages:

   • Simple and easy to implement
   • Works with both sorted and unsorted lists
   • No additional memory required
   • Best for small lists or when searching rarely

2. Performance Considerations:

   • Not efficient for large datasets
   • Time complexity grows linearly with list size
   • Consider using Binary Search for sorted lists

3. Best Use Cases:

   • Small lists (n < 100)
   • Unsorted data
   • One-time searches
   • When simplicity is preferred over efficiency