Linear search, also known as sequential search, is a simple searching algorithm that checks each element of a list in order until a match is found or the entire list has been traversed.
Algorithm Steps
Start at the beginning of the list.
Compare the target value with the current element.
If the target value matches the current element, the search is successful and the position of the element is returned.
If the target value does not match the current element, move to the next element in the list.
Repeat steps 2-4 until a match is found or the end of the list is reached.
What is a linear search?
A linear search algorithm is an algorithm that looks at every in a list or an array until it finds the target value.
Time & Space Complexity
Time complexity - O(n)
Because linear search potentially needs to check each item (n) in the list once in the list, the time complexity is O(n)
Space complexity O(1)
The space complexity of a linear search algorithm is generally O(1), which means it uses a constant amount of additional memory regardless of the size of the input data. This is because a linear search does not require any additional data structures or memory allocation that scales with the size of the input.
You may use a few variables for control and temporary storage, but the memory usage remains constant and doesn't depend on the size of the input data.
What is the worst-case time complexity of linear search?
Pros and Cons of Linear Search
Advantages
Simple and easy to understand
Works on both sorted and unsorted lists
Works well for small data sets
Useful if you expect the item to be near the beginning of the list
Disadvantages
Inefficient for large data sets
Time complexity: O(n), where n is the size of the list
Can be slow compared to other search algorithms
In which situation is linear search usually the most efficient?
