Linear Search Algorithm

Linear search is a simple search algorithm that searches for a target value in a list of elements. It compares each element of the list to the target value until a match is found or the whole list has been searched.

function linearSearch(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) {
      return i;
    }
  }
  return -1;
}
 
const arr = [1, 2, 3, 4, 5];
const target = 3;
console.log(linearSearch(arr, target)); // Output: 2

Time Complexity

The time complexity of the linear search algorithm is O(n) where n is the number of elements in the list. This is because in the worst-case scenario, the algorithm will have to search through all n elements of the list to find the target value.

Space Complexity

The space complexity of the linear search algorithm is O(1) because it only requires a constant amount of extra space to store the target value and the index of the target value if it is found.

Time and Space Complexity of Linear Search Algorithm:

Best Case Time Complexity: O(1) - The target value is found at the first index of the list.
Average Case Time Complexity: O(n) - The target value is found at the middle of the list.
Worst Case Time Complexity: O(n) - The target value is found at the last index of the list.

Applications

Linear search is useful when the list of elements is sorted or unsorted .
Linear search can be used to find the first occurrence of a target value in a list.
Linear search can be used to find the index of a target value in a list.
Small data sets where the overhead of more complicated algorithms is not justified.

Advantages of Linear Search Algorithm:

Simple and easy to implement.
Works on sorted and unsorted lists.
Does not require any extra memory space.
Useful for small data sets.

Disadvantages of Linear Search Algorithm:

Inefficient for large data sets.
Not suitable for large data sets arrays.
Time complexity is O(n) which is not efficient for large data sets.
Slower than other search algorithms like binary search and hash tables.

When to use Linear Search Algorithm?

When the list of elements is small.
When the list of elements is unsorted.
When data set sorted contiguous memory locations.
When the target value is not present in the list.

Frequently Asked Questions:

What is the linear search algorithm?

The linear search algorithm is a simple search algorithm that searches for a target value in a list of elements. It compares each element of the list to the target value until a match is found or the whole list has been searched.

What is the time complexity of the linear search algorithm?

The time complexity of the linear search algorithm is O(n) where n is the number of elements in the list.

How does linear search algorithm work?

The linear search algorithm works by iterating through each element of the list and comparing it to the target value. If the element matches the target value, the algorithm returns the index of the element. If the target value is not found in the list, the algorithm returns -1.

What is the space complexity of the linear search algorithm?

The space complexity of the linear search algorithm is O(1) because it only requires a constant amount of extra space to store the target value and the index of the target value if it is found.

What are the advantages of the linear search algorithm?

The advantages of the linear search algorithm are:

Simple and easy to implement.
Works on sorted and unsorted lists.
Does not require any extra memory space.
Useful for small data sets.

What are the disadvantages of the linear search algorithm?

The disadvantages of the linear search algorithm are:

Inefficient for large data sets.
Not suitable for large data sets arrays.
Time complexity is O(n) which is not efficient for large data sets.
Slower than other search algorithms like binary search and hash tables.

When to use the linear search algorithm?

The linear search algorithm can be used when:

The list of elements is small.
The list of elements is unsorted.
The data set sorted contiguous memory locations.

What are the applications of the linear search algorithm?

The applications of the linear search algorithm are:

Linear search is useful when the list of elements is sorted or unsorted.
Linear search can be used to find the first occurrence of a target value in a list.
Linear search can be used to find the index of a target value in a list.
Small data sets where the overhead of more complicated algorithms is not justified.

When is linear search algorithm preferred over other searching algorithms?

The linear search algorithm is preferred over other searching algorithms when:

The list of elements is small.
The list of elements is unsorted.
The data set sorted contiguous memory locations.

Can linear search algorithm be applied to other data structures?

Yes, the linear search algorithm can be applied to other data structures like arrays, linked lists, and hash tables. The algorithm can be modified to work with different data structures by changing the way the elements are accessed and compared.

Searching Algorithms Binary Search