Linear Search

Linear search is the simplest searching algorithm. It works by checking each element in the list one by one, starting from the beginning, until it finds the item you're looking for. Working of Linear Search 1. Suppose we need to find element k = 6 listed below. 2. Start from the first element, compare k with each element x. 3. If x == k, return the index. 4. Else, return not found. Linear Search Algorithm LinearSearch(array, key) for each item in the array if item == value return its index Linear Search Code function linearSearch(arr, key){ for (let i = 0; i

Apr 10, 2025 - 18:44

Linear search is the simplest searching algorithm. It works by checking each element in the list one by one, starting from the beginning, until it finds the item you're looking for.

Working of Linear Search

1. Suppose we need to find element k = 6 listed below.

2. Start from the first element, compare k with each element x.

3. If x == k, return the index.

4. Else, return not found.

Linear Search Algorithm

LinearSearch(array, key)
  for each item in the array
    if item == value
      return its index

Linear Search Code

function linearSearch(arr, key){
  for (let i = 0; i < arr.length; i++)  if (arr[i] === key) return i

  return "not found";
};

console.log(linearSearch([1, 2, 4, 5], 4));

Linear Search Complexities

Time Complexity
Best	O(1)
Worst	O(n)
Average	O(n)
Space Complexity	O(1)
Stability	N/A

1. Time Complexities

Best Case: O(1)
When the target element is the first item in the list, it's found immediately.
Worst Case: O(n)
When the target is the last element or not in the list at all. We have to check every item.
Average Case: O(n)
On average, the target is somewhere in the middle of the list, so about half the elements are checked.

2. Space Complexity

Space Complexity: O(1) Linear search uses no extra space, it just checks elements one by one.

Applications of Linear Search

1. Unsorted Data

Linear search works well on unsorted or unstructured data where sorting is not possible or needed.

2. Small Data Sets

Ideal for small lists where performance isn’t a concern.

3. Searching in User Input

Used in basic input validation where the system checks for a value in a list of allowed values.

4. Search in Linked Lists

Since linked lists don’t allow direct access by index, linear search is a good fit.

5. Browser History or Chat Search

Quickly check if a particular URL or message exists.

6. Finding Duplicate Entries

Check through each element to find any repeated items.

7. Educational Purpose

Great for teaching basic search concepts before moving to more complex algorithms like binary search.