# Linear Search in Data Structures - Infovistar

### Linear Search or Sequential Search

Sequential search is also known as Linear Search.

In Sequential search, elements are examined sequentially starting from the first element. It examines all values in an array until it finds a match or reaches the end.

It is the simplest search algorithm. In linear search, each element of the list is matched with the item whose location is to be found, by traversing the list completely.

If the match is found, the algorithm returns the item's location; otherwise, it returns NULL.

Linear search has a worst-case time complexity of O(n).

Algorithm for searching an element `key` in an array `a[]` having n elements.

### Simple Sequential Search

Linear search has a time complexity `O(n)`. Such algorithms are not suitable for searching when the number of elements is large.

### Time Complexity

Case Time Complexity
Best Case O(1)
Average Case O(n)
Worst Case O(n)
• Best Case O(1): It occurs when the element we are finding is at the first position of the array.
• Average Case O(n): Linear search has an average case time complexity of O(n)
• Worst Case O(n): The worst case scenario in linear search is when the target element doesn't exist in the given array, and we have to traverse the entire array.

The Linear search has a time complexity of O(n), because each element in the array is compared once.

### Space Complexity

Linear search has a space complexity of O(1).