Linear Search

Linear search, also known as sequential search, is a fundamental algorithm used to find a specific element within a list. It operates by starting at the beginning of the list and examining each element one by one until the target element is found or the end of the list is reached. This method is straightforward and does not require the list to be sorted, but it can be inefficient for large datasets.

Algorithm Workflow

The linear search algorithm follows these steps:

1. Start from the first element of the list.
2. Compare the current element with the target element.
   • If they are equal, return the index of the current element.
   • If not, move to the next element.
3. Repeat step 2 until the target element is found or the end of the list is reached.
4. If the end of the list is reached without finding the target element, return an indication that the search was unsuccessful (e.g., -1).

Pseudocode

LinearSearch(list, target_element):
    FOR each item in list WITH index i:
        IF item == target_element THEN
            RETURN i
    RETURN -1

Complexity Analysis

Time Complexity

• Best Case: $O(1)$
  • The target element is the first element in the list.
• Average Case: $O(n)$
  • On average, the algorithm checks half of the elements.
• Worst Case: $O(n)$
  • The target element is the last element or not present at all.

Here, $n$ represents the number of elements in the list.

Space Complexity

• Space Complexity: $O(1)$
  • Requires a constant amount of additional space regardless of input size.

Applications

Linear search is particularly useful when:

• The list is unsorted.
• The list is small.
• Searches are performed infrequently or only once.

Limitations

• Inefficient for large datasets.
• Not optimal when multiple searches are required on the same list.
• More efficient algorithms like binary search (for sorted lists) or data structures like hash tables are preferred for better performance.

Note: While linear search is simple and easy to implement, its inefficiency for large datasets makes it less practical for performance-critical applications.