Linear Search Visualization: Step-by-Step Animation
Watch linear search scan through an array element by element until it finds the target value.
def linear_search(arr, target):
for i in range(len(arr)):
if arr[i] == target:
return i
return -1Array State
About This Linear Search Animation
The interactive visualization above demonstrates how linear search works on an unsorted array of integers. We are searching for the target value 22. The animation shows the algorithm checking each element one by one, with the Python code highlighted line-by-line as each step executes.
Use the example tabs above the animation to explore different scenarios: finding an element after several comparisons, best-case performance (found immediately), and worst-case when the target is not in the array at all.
In the Animation Panel on the right, the current element being examined is highlighted in amber with the i marker showing the current index. When the target is found, it turns green. Unlike binary search, there are no low/high pointers because linear search simply scans from left to right.
What is Linear Search?
Linear search (also called sequential search) is the simplest searching algorithm in computer science. It works by iterating through each element of a collection one by one, comparing each element to the target until a match is found or the end of the collection is reached.
The key advantage of linear search is its simplicity and versatility. Unlike binary search, which requires sorted data, linear search works on any data structure that supports sequential access - arrays, linked lists, streams, or any iterable. This makes it the go-to algorithm when your data is unsorted or when sorting would be too expensive.
The algorithm follows a simple, sequential process:
- Start at the first element (index 0) of the list.
- Compare the current element with your target value.
- If they match, return the current index (success).
- If they don't match, move to the next element.
- Repeat until a match is found or the end of the list is reached.
- If the end is reached without a match, return -1.
Time and Space Complexity
In the worst case, we must check every element in the array. Best case is O(1) if the target happens to be the first element. Average case is O(n/2), which simplifies to O(n).
Linear search only uses a single variable to track the current index, regardless of the input size. No additional data structures are needed.
When to Use Linear Search
Despite its O(n) time complexity, linear search is often the right choice in certain scenarios. Understanding when to use it is just as important as knowing how it works:
- The data is unsorted and sorting would be too expensive or impractical
- The dataset is small (less than ~100 elements), where the overhead of binary search is not worth it
- You are searching a linked list where random access is O(n) anyway
- The data is streaming or you can only read it once (no random access)
- You need to find all occurrences of a target, not just the first
- The search is a one-time operation and the data will not be reused
- The data structure does not support random access (generators, iterators, file streams)
Linear Search vs Binary Search
The choice between linear and binary search depends on your specific situation. Here is a detailed comparison:
| Aspect | Linear Search | Binary Search |
|---|---|---|
| Time Complexity | O(n) | O(log n) |
| Requires Sorted Data | No | Yes |
| Works on Linked Lists | Yes (efficient) | No (O(n) per access) |
| Implementation Difficulty | Very Simple | Tricky (off-by-one errors) |
| 1 Million Elements | Up to 1M comparisons | At most 20 comparisons |
Common Mistakes and How to Avoid Them
While linear search is simple, there are still some common pitfalls to watch out for:
- Modifying the array during iteration: If you delete or insert elements while iterating, you may skip elements or cause index errors. Either iterate over a copy or collect indices first and modify afterward.
- Not handling empty arrays: Always check if the array is empty before searching. The loop will simply not execute, but make sure your return value is correct.
- Using linear search when binary search is better: If you are searching the same sorted array multiple times, the O(n log n) cost of sorting once plus O(log n) per search beats O(n) per search after just a few queries.
- Stopping too early with duplicates: If you need all occurrences, do not return on the first match. Collect all matching indices or use a callback pattern.
Variations of Linear Search
The basic linear search can be optimized or adapted for different use cases:
Sentinel Linear Search
Place the target at the end of the array as a "sentinel". This eliminates the bounds check in each iteration (we only check arr[i] == target, not also i < n), making it slightly faster. After the loop, check if the found index is the sentinel position.
Bidirectional Linear Search
Search from both ends simultaneously using two pointers. This can find the target faster on average if it is near either end of the array. The worst case is still O(n/2), but average performance improves for many distributions.
Find All Occurrences
Instead of returning on the first match, continue searching and collect all indices where the target appears. Return a list of indices (empty list if not found).
Search with Predicate
Instead of exact match, pass a function that determines if an element matches. This enables searching for elements that satisfy complex conditions (e.g., first even number greater than 10).
Master the Algorithms That Matter
Linear search is simple, but knowing when to move beyond it is what separates junior from senior engineers. To pass modern technical interviews, you need to master the high-efficiency patterns that optimize these brute-force approaches.
TerminalTales is a story-driven DSA course that focuses on the patterns that actually get asked, like Two Pointers, Sliding Window, and Binary Search. We skip the academic fluff and double down on what gets you hired.
What You Will Learn
- When linear search is actually the better choice over binary search
- Pattern recognition to instantly identify the right search algorithm
- Key variations like binary search and two pointers
- Spaced repetition reviews to lock in your knowledge permanently
Start with 3 free chapters and experience the difference that story-driven learning makes. Join thousands of engineers who have used TerminalTales to land their dream jobs at top tech companies.
Related Algorithms
Master DSA with Story-Driven Learning
TerminalTales combines an immersive narrative with spaced repetition to help you actually remember what you learn.
Start Learning Free