Chapter 9: DSA Linear Search
DSA Linear Search – Let’s understand this topic like I’m your friend sitting next to you in the library, explaining it slowly, clearly, with real examples, visuals in words, code, and honest comments about when you actually use it.
What is Linear Search?
Linear Search (also called Sequential Search) is the simplest and most straightforward searching algorithm.
Its core idea is very easy:
Start from the first element of the array/list Check one by one whether this element is the one we are looking for If found → return its position If you reach the end without finding it → it’s not present
That’s literally it.
No fancy logic, no sorting required, no preprocessing — just check everything in order.
Real-life analogy
Imagine you are searching for your blue notebook in a big messy shelf of 50 books.
You start from the leftmost book:
- Is this blue? No
- This one? No
- This one? No
- …
- Ah! This one is blue → found it!
You checked one book at a time from start to end. That’s exactly linear search.
When is Linear Search used in real life?
- Small lists (10–100 items)
- When the list is not sorted
- When you search very rarely (not worth sorting first)
- When data comes one by one (streaming data)
- As a fallback when better methods cannot be used
- In many real-world menus, recent items, small dropdowns
Step-by-step example
Array: [17, 42, 8, 95, 31, 64, 12, 5, 88]
We want to find 31.
Start from index 0:
Index 0: 17 ≠ 31 Index 1: 42 ≠ 31 Index 2: 8 ≠ 31 Index 3: 95 ≠ 31 Index 4: 31 == 31 → Found at position 4
If we were looking for 100:
We would check all 9 elements → not found → return -1 or “not found”
Linear Search Code – Very Clear Versions
1. Basic version – returns index or -1
|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
def linear_search(arr, target): for i in range(len(arr)): if arr[i] == target: return i # found → return index return -1 # not found # Example numbers = [17, 42, 8, 95, 31, 64, 12, 5, 88] print(linear_search(numbers, 31)) # Output: 4 print(linear_search(numbers, 100)) # Output: -1 |
2. Version that tells position in human language
|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 |
def find_item(arr, target): for position in range(len(arr)): if arr[position] == target: return f"Found {target} at position {position} (index {position})" return f"{target} is not in the list" print(find_item([10, 20, 30, 40], 30)) # Output: Found 30 at position 2 (index 2) |
3. Searching in list of strings
|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
friends = ["rahul", "priya", "aman", "sneha", "rohan"] def find_friend(name): for i in range(len(friends)): if friends[i].lower() == name.lower(): return i return -1 print(find_friend("Sneha")) # Output: 3 |
Time & Space Complexity (must know for interviews)
| Case | Time Complexity | Explanation |
|---|---|---|
| Best Case | O(1) | Target is at first position |
| Average Case | O(n) | |
| Worst Case | O(n) | Target is at last position or not present |
| Space Complexity | O(1) | Only uses a few variables |
Very simple: time grows linearly with the size of the array.
Comparison: Linear Search vs Binary Search
| Feature | Linear Search | Binary Search |
|---|---|---|
| Prerequisite | No need to sort | Array must be sorted |
| Time complexity | O(n) | O(log n) |
| Best case | O(1) | O(1) |
| Worst case | O(n) | O(log n) |
| Works on unsorted data? | Yes | No |
| Ease of implementation | Very easy | A bit more code |
| Use case | Small / unsorted / rare search | Large sorted data |
Rule of thumb interviewers love:
If array is unsorted or small → use Linear Search If array is sorted and large → use Binary Search
When should you actually use Linear Search in real code?
Yes – use it when:
- List size is small (< 100–500 elements)
- Data is not sorted and sorting would be expensive
- You are doing one-time search (no repeated searches)
- You are searching in linked list (no random access)
- You are searching in streaming data (data coming one by one)
- You want simplest possible code
No – prefer better methods when:
- Array is large and sorted → Binary Search
- You have many searches → sort once + Binary Search
- You want O(1) average lookup → Hash Set / Hash Map
Common Interview Questions based on Linear Search idea
- Find first occurrence of a number
- Find last occurrence of a number
- Find all positions where target appears
- Count how many times a number appears
- Find minimum / maximum element (this is also linear search kind of logic)
- Check if array contains any duplicate
- Find the first missing positive number (variation)
Summary – Linear Search in one line each
- Simplest searching method
- Checks every element one by one from start to end
- No need for sorted data
- Time complexity O(n) in worst and average case
- O(1) extra space
- Very easy to write and understand
- Good for small lists, unsorted data, linked lists, one-time searches
- Starting point of almost every searching topic in DSA
Now that you’ve understood Linear Search properly…
Would you like to move to the next logical topic?
Some popular choices:
- Binary Search (the natural next step)
- How to find first and last position of an element
- Linear search on linked list vs array
- Common interview problems that look like linear search
- When interviewers ask “Can you do better than O(n)?”
Just tell me which one you want next — I’ll explain it in the same detailed, friendly way! 😄
