Linear Search
Introduction to Linear Search
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?
Linear Search Visualisation
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?
Review: Fill in the Blanks
The time complexity of linear search is because it potentially needs to check each item in the list once, where n is the size of the list. The space complexity is typically O(1) since it uses a amount of additional memory, regardless of the size of the input data. This means that while you may use a few variables for control and temporary storage, the usage remains constant and does not depend on the size of the input data.
There are several advantages to using linear search, such as being and easy to understand, making it effective for both sorted and unsorted lists. It works well for small data sets and is particularly useful if the expected item is near the of the list. However, there are also disadvantages, including being inefficient for data sets, having a time complexity of O(n), and being slower compared to other more advanced search algorithms.
Complete! Ready to test your knowledge?
Linear Search
- Introduction to Linear Search
- Linear Search Visualisation
- Time & Space Complexity
- Pros and Cons of Linear Search