Linear Search
Check every item from left to right until you find the key or run out. Works on any array, sorted or not, but costs O(n).
Rule of this site: Don't just watch: implement it yourself, then solve 2–3 problems.
02Mental model
Looking for your friend in a queue of strangers, you walk from the front and check each face until you see them, or reach the end. That’s linear (sequential) search.
The algorithm
for each index i from 0 to n-1:
if a[i] == key: return i
return -1 (only after checking everything)Strengths and weaknesses
- ✅ Works on unsorted data and on linked lists.
- ✅ Dead simple, no preparation needed.
- ❌ Slow for big data: up to n comparisons.
If you’ll search the same large array many times, it’s worth sorting it once and using binary search after that.
03Visualize
space play · ←→ step · r reset. The highlighted code line follows each step.
Search for a value that is present, then one that is missing.
04C++ code
Compiled and run with g++ -std=c++17; the output below is real. Type it out yourself before you copy it.
#include <iostream>
using namespace std;
int linearSearch(const int a[], int n, int key) {
for (int i = 0; i < n; i++)
if (a[i] == key)
return i; // found: stop right away
return -1; // checked everything: not there
}
int main() {
int a[] = {23, 7, 41, 15, 9, 32, 18};
int n = 7;
cout << "search 9 -> " << linearSearch(a, n, 9) << "\n";
cout << "search 23 -> " << linearSearch(a, n, 23) << "\n";
cout << "search 50 -> " << linearSearch(a, n, 50) << "\n";
}search 9 -> 4 search 23 -> 0 search 50 -> -1
05Complexity
| Best case | O(1): key at index 0 |
|---|---|
| Average case (found) | (n + 1)/2 comparisons → O(n) |
| Worst case | O(n): last item or not present |
| Needs sorted data? | No |
| Extra space | O(1) |
On a linked list, linear search is the only option, because you can't jump to the middle.
06Watch
What is binary search
Why this one: Starts with linear search, then shows why binary search is a huge improvement.
Original class slides (Python, by the course's lecture authors):Sorting Basics
07Exam lens
Likely questions
- Write a linear search function that returns the index of the key or −1.
- What are the best, average and worst case complexities of linear search?
- When is linear search preferred over binary search?
- Modify linear search to return the index of the LAST occurrence.
Common mistakes
- Returning
-1inside the loop (in anelse), which stops after checking only the first item. - Looping with
i <= n, one past the end. - Forgetting that an unsorted array cannot use binary search.
08Quick check
09Practice
🟢 Trace by hand
How many comparisons does linear search make on [7, 2, 9, 4, 9, 1] for keys 9, 1 and 5?
Show answer
- key 9: 3 (first occurrence at index 2)
- key 1: 6
- key 5: 6 (not found)
🟡 Implement it
Write countOccurrences(a, n, key) and lastIndexOf(a, n, key).
Hint
For lastIndexOf, loop backwards from n - 1 and return the first match, or loop forwards and remember the latest match.
🔴 Solve problems
Hint
For each item, linearly search for its double (O(n²)). Then think about how a set makes it O(n).
Hint
A linear scan with a digit counter.
10Mastery checklist
Tick these honestly. When every box is ticked, the topic is marked complete.