Overview
Linear Search scans each element until it finds the target or reaches the end.
Analogy
Looking for a book on an unsorted shelf by checking every spine in order.
Step-by-step
- Start at index 0.
- Compare arr[i] to target.
- If equal, return i.
- Else increment i and continue.
- If end reached, return not found.
Visual
[7 2 9 4] → check 7 (no) → check 2 (yes at index 1).
Common mistakes
- Using i < n-1 and skipping last element.
- Not handling empty array.
- Using linear search on sorted data where binary search is better.
Practice questions
- Count comparisons for best, worst, average.
- Return all indices of a target.
- Search from both ends simultaneously and compare steps saved.
AI Wisdom