Core Concept Mastery • DSA Module
Linear search means you start at the beginning of the list and check every item one by one until you find the target or reach the end. It works on any list, sorted or not. Best case: target at the start (O(1)). Worst case: target at the end or missing (O(n)).
Imagine looking for Ketchup in a messy aisle. You start at the beginning and look at every bottle until you find it.
Start at the beginning. Check every item one by one until you find the target or reach the end.
Checking one by one. O(n).
| Case | Time | Scenario |
|---|---|---|
| Best | O(1) | Target is the first item. |
| Worst | O(n) | Target is at the end or not in the list. |
The strategy
Start at index 0. Look at the first item. Is it the target? If yes, you are done. If no, go to the next item. Repeat until you find the target or run out of items.
Like a grocery aisle
Imagine looking for ketchup in a messy aisle. You start at one end and look at every bottle until you find it. You do not jump around. That is linear search.
Time complexity
When to use it
Use linear search when the list is unsorted or when the list is small. It is simple and always correct.
When the list is not sorted, or when the list is small, linear search is simple and good enough. When the list is huge and sorted, binary search is much faster.