Move it step by step
Searching array [3, 8, 12, 17, 23, 31, 42, 56] for 42
- 30
- 81
- 122
- 173
- 234
- 315
- 426
- 567
- comparing
- found
- different
- The number under each box is its index
Step 1 of 9Comparisons: 0
We're looking for 42. We'll check from the leftmost index, 0, one by one.
The pseudocode line currently running
- 1for i from 0 to n - 1:
- 2if a[i] == x:
- 3return i (found)
- 4return -1 (not found)
Change the example
Try predicting
You're on step 1.
Which index will be compared next?
What you'll learn
- The flow of searching an array by comparing values one by one from the left
- Why the number of comparisons grows in proportion to the array's length
Prerequisites
- Arrays and indices (numbering that starts at 0)
- Writing a for loop that takes out one value at a time
How this search works
Linear search compares values in order from the left end of the array and stops as soon as it finds one equal to the target.
It works no matter how the array is ordered. The tradeoff is that, if you're unlucky, it compares every single value before finishing.
Steps, with an example
- 1Compare the value at index 0 with the target value
- 2If they match, that index is the answer, and we're done
- 3If they differ, move one step to the right and repeat
- 4If we reach the right end without a match, we finish with "not found"
| # | Compared at | Result |
|---|---|---|
| 1 | Index 0: 3 | Different. Move right |
| 2 | Index 1: 8 | Different. Move right |
| 3 | Index 2: 12 | Different. Move right |
| 4 | Index 3: 17 | Different. Move right |
| 5 | Index 4: 23 | Different. Move right |
| 6 | Index 5: 31 | Different. Move right |
| 7 | Index 6: 42 | Same. Found |
Comparisons and complexity
| Case | Comparisons | Complexity |
|---|---|---|
| Best case | 1 comparison (value is at the left end) | O(1) |
| Average | About n ÷ 2 comparisons | O(n) |
| Worst case | n comparisons (value is at the right end, or not present) | O(n) |
n is the length of the array. With 8 elements, the worst case is 8 comparisons; with 1,000,000 elements, it's 1,000,000 comparisons.
| Target | Linear search | Binary search |
|---|---|---|
| 42 | 7 | 3 |
| 20 | 8 | 3 |
| 3 | 1 | 3 |
| 56 | 8 | 4 |
When to use it
Good fit
- The array isn't sorted
- The array is small, with up to a few dozen elements
- You're only searching once, so sorting first would cost more than it saves
Not a good fit
- A large array you'll search many times (use binary search instead)
- You want to look values up directly by key (use a dictionary or hash table instead)
Code
Pseudocode
- 1for i from 0 to n - 1:
- 2if a[i] == x:
- 3return i (found)
- 4return -1 (not found)
Working code
▶ Press “Run” to see the result here
Edit the Python or JavaScript and press “Run” to see the result right away. Java is read-only here.
FAQ
- How is this different from Python's `in` or `.index()`?
- Both `x in a` and `a.index(x)` compare values from the left internally, the same way. Writing linear search yourself makes that work visible.
- If the same value appears twice, which index is returned?
- Since we compare from the left, the leftmost matching index is returned first.
- Why return -1 when the value isn't found?
- Since indices are always 0 or greater, -1 is an impossible value, so it's used as a marker for "not found". Some languages instead return None or null.
