Linear Search — The Foundation of Searching

What Is Linear Search?

Linear Search is the most fundamental search algorithm. It scans every element of a list one by one from left to right until it finds the target — or exhausts the entire list.

No preconditions. No sorting required. Just iterate and compare.

---

Why Use It?

Linear search shines in situations where:

• The array is unsorted (binary search can't help you)
• The array is very small (overhead of sorting isn't worth it)
• You need to find the first element matching a condition, not just an exact value

---

The Algorithm

1. Start at index 0
2. Compare nums[i] with target
3. If they match, return i
4. Otherwise increment i and repeat
5. If the end is reached, return -1

• Time Complexity: O(N) — worst case we check every element
• Space Complexity: O(1) — no extra memory needed

---

Interactive Lab

Watch the pointer scan each element until the target is found.

---

When Linear Search Beats Binary Search

Scenario	Best Choice
Unsorted array	Linear Search
Sorted array, large N	Binary Search
Tiny array (< 10 elements)	Linear Search (simpler)
Searching by a condition (not exact match)	Linear Search

---

Key Takeaway

Linear search is the algorithm you instinctively perform when scanning a list by eye. It's O(N) — meaning doubling the input doubles the work. For large sorted datasets, use Binary Search instead. But for small or unsorted data, linear search is perfectly fine.