Linear Search
Sequentially checks each element of the list until a match is found or the whole list has been searched.
Find Target:
Ready to search
Intuition
Imagine you are looking for a specific book on a messy bookshelf where the books are not organized. To find it, you have to look at the first book, then the second, then the third, and so on, until you find the one you want or reach the end of the shelf. This checking "one by one" is exactly how Linear Search works.
Concept
Linear Search is the simplest search algorithm. It checks every element in the list sequentially, starting from the first element, until a match is found or the entire list has been traversed. It runs in O(n) time complexity.
How it Works
- Start at the first element (index 0).
- Compare the current element with the target value.
- If they match, return the current index (Success!).
- If they don't match, move to the next element.
- Repeat until you find the target or run out of elements.
- If you reach the end without finding it, return -1 (Not Found).
Step-by-Step Breakdown
- Start at the beginning: Point your finger at the first item.
- Check it: Is this the item you are looking for?
- Yes? You're done! Stop searching.
- No? Move your finger to the next item.
- Keep going: Repeat this for every single item in the line.
- Give up? If you reach the end and haven't found it, it's not there.
Trace: Search 30 in [10, 50, 30, 70]
Check Index 0
Compare arr[0] (10) with Target (30).
10 != 30. Continue.
Check Index 1
Compare arr[1] (50) with Target (30).
50 != 30. Continue.
Check Index 2
Compare arr[2] (30) with Target (30).
30 == 30. Found!
Found
Return index 2.
When to Use
- Unsorted Data: It is the only way to search if the list is not sorted.
- Small Datasets: For very small lists, it's fast enough and easy to implement.
- Linked Lists: You cannot jump to the middle of a linked list, so you must use linear search.
When NOT to Use
- Large Sorted Datasets: Binary Search is much faster (O(log n) vs O(n)).
- Frequent Searches: If you search the same large list many times, it's better to sort it first or use a Hash Map.
How to Identify
You will rarely be asked to implement "Linear Search" explicitly. However, iterating through an array to find an element, find the max/min, or count occurrences are all variations of Linear Search. Look for keywords like "Unsorted", "Find first occurrence", or searching in a Linked List.
Frequently Asked Questions
When should I use Linear Search?
Use Linear Search for small datasets or when the data is unsorted. It is the simplest search algorithm but has O(n) complexity.
What is the time complexity of Linear Search?
The average and worst-case complexity is O(n), as you may need to scan every element. The best case is O(1) if the target is the first element.
Linear vs Binary Search?
Linear Search works on any array, while Binary Search requires the array to be sorted and is significantly faster (O(log n)).