Searching Algorithms•Easy

Linear Search

Linear Search Algorithm

Linear Search (also known as Sequential Search) is the simplest searching method. It starts at the beginning of a collection (such as an array or a list) and examines every element one-by-one sequentially until the target element is found or the end of the collection is reached.

How It Works

Imagine searching for a specific card in an unsorted deck of playing cards. You flip the cards one by one from the top until you find the card you are looking for.

Algorithm Steps:

  1. Start at the first element (index 0).
  2. Compare the current element with the target key.
  3. If they match, return the current index.
  4. If they do not match, move to the next element (increment index by 1) and repeat step 2.
  5. If the end of the array is reached and the key was not found, return -1.

Advantages & Disadvantages

Advantages ✅

  • No Sorting Required: Works on both sorted and unsorted lists.
  • Easy to Implement: Very simple and intuitive code structure.
  • Memory Efficient: Operates in-place with O(1) auxiliary space.
  • Efficient for Small Data: Performs well on lists with very few elements.

Disadvantages ❌

  • Poor Scalability: Highly inefficient for large lists with millions of elements.
  • Slow Average/Worst Case: On average, it scans half the list; in the worst case, it scans all N elements.

Complexity Analysis

  • Time Complexity:
    • Best Case: O(1) when the target element is located at the very first index (index 0).
    • Average Case: O(N) when the target is in the middle of the list.
    • Worst Case: O(N) when the target is at the last index or not present in the collection.
  • Space Complexity: O(1) auxiliary space since no extra memory buffers are allocated.