Linear Search
The simplest search there is — look at each item in turn until you find what you want. Slow when the data is huge, but often exactly right.
What you'll learn
- How linear search checks each element in order and reports the position, or that the value is absent, in O(n) time
- Why it needs no setup at all — unsorted, messy, one-off data is no problem
- That Python's `in` and `.index()` are linear searches underneath
- When a plain scan genuinely beats a cleverer algorithm
Before you start
Suppose someone hands you a shuffled stack of exam papers and asks you to pull out Meera’s.
There is no order to exploit — the papers could be in any arrangement — so you do the only sensible thing. You look at the top paper; if it is not hers, you set it aside and look at the next; and you keep going until her name turns up or the stack runs out. That is the whole of linear search, and its plainness is exactly the point.
Looking at each item in turn
Let us make it concrete. Here are eight temperature readings, in no particular order:
[22, 18, 35, 12, 29, 41, 7, 33]To find 29, we begin at the left and compare each reading with our target, one at a time:
22? no 18? no 35? no 12? no 29? yes — found, at index 4Five looks. And to search for a value that is not there at all — say 99 — there is no shortcut: we have to check all eight before we can be sure it is missing. That “check everything to be certain” is the price of having no order to lean on.
In code, the loop is as short as the idea:
def linear_search(arr, target):
for i, value in enumerate(arr):
if value == target:
return i # found it — hand back the position
return -1 # fell off the end — not here
temps = [22, 18, 35, 12, 29, 41, 7, 33]
print(linear_search(temps, 29)) # the index of 29
print(linear_search(temps, 99)) # 99 is not presentThis prints:
4
-1When the target is the last element, or missing entirely, we make n comparisons for n items. That is the worst case, and it is O(n): double the data, double the work.
You have already used linear search without writing it. Python’s in and .index() run this very loop on your behalf:
29 in temps # the same scan, stopping at the first match
temps.index(29) # the same scan, raising ValueError if absentWriting it out by hand simply makes the comparisons visible.
When a plain scan is the right call
Binary search — the next lesson — is faster, O(log n), but it demands a sorted array, and sorting costs O(n log n). That trade-off is what decides which tool fits.
Reach for linear search when:
- The data is unsorted and you need one lookup. Sorting a ten-item list just to binary-search it once is pure overhead.
nis small. Below a few hundred items, the gap between O(n) and O(log n) is a handful of nanoseconds; the simpler code wins.- It is a one-off. Search the same data thousands of times and an index pays off; search it once and a scan is fine.
- The items only support equality, not ordering. You cannot binary-search objects you cannot sort.
Practice
Quick check
Practice this in an interview
All questionsBinary search halves the search space each iteration to find a target in O(log n). The tricky part is not the idea but the boundary conditions: closed vs. half-open intervals, how to update lo/hi, and when to use lo < hi vs. lo <= hi. One clean template eliminates all the classic bugs.
Even after rotation, one of the two halves around mid is always fully sorted. Check which half is sorted, then decide whether the target falls inside it. If yes, narrow to that half; if no, search the other. This keeps binary search's O(log n) guarantee.
Binary search on the answer space (eating speed 1 through max pile size) rather than on the input array. For each candidate speed, greedily compute hours needed in O(n). The feasibility check is monotone — if speed k works, any speed above k also works — so binary search finds the minimum valid speed in O(n log m) time.
Hybrid search combines dense vector similarity with sparse keyword search such as BM25, then fuses the rankings. Dense retrieval captures semantic meaning while keyword search nails exact terms, identifiers, and rare tokens, so combining them improves recall and precision over either alone.