Linear Search
The simplest search algorithm — scan items one by one until you find what you need. Slow at scale, but often exactly right.
What you'll learn
- Linear search checks each element in order and returns the index or -1 in O(n) time
- No precondition is needed — unsorted, messy, or one-off data is fine
- Python's built-in `in` and `.index()` are linear searches under the hood
- When n is small or sorting first would cost more than the search saves, linear beats binary
Before you start
The most direct search strategy: start at the first element and look at each one in turn until you find the target — or run out of elements. No tricks, no prerequisites. That simplicity is both its limitation and its appeal.
How it works
Walk the array from index 0 to index n-1. At each step, compare the current element to the target. If they match, you’re done. If you reach the end without a match, return -1.
In the worst case — the target is last, or absent — you make n
comparisons. That’s O(n).
Python’s built-in in operator and .index() do exactly this scan
internally:
29 in temps # same loop, stops at first match
temps.index(29) # same loop, raises ValueError if missingWriting it yourself just makes the comparison count visible.
Step through a search and count the comparisons:
When linear search is the right call
Binary search is faster — O(log n) — but it requires a sorted array. Sorting costs O(n log n). That trade-off matters.
Use linear search when:
- The data is unsorted and you need only one lookup. Sorting to binary-search a 10-element list is pure overhead.
- n is small. For lists under a few hundred elements the difference between O(n) and O(log n) is nanoseconds. Reaching for a more complex algorithm adds code for zero practical gain.
- You’re doing a one-off scan. If you’ll search the same data thousands of times, build an index. If you’ll search it once, linear is fine.
- Elements aren’t comparable or orderable — you can’t sort objects that only support equality checks.
Quick check
Quick check
What’s next
Now that you’ve seen the baseline, the next lesson introduces binary search: the same problem, but on sorted data, cutting the search space in half with each comparison.
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.
A B-tree index stores key values in a balanced tree of sorted nodes, allowing the engine to reach any value in O(log n) page reads instead of scanning every row. The optimizer skips the index when the estimated cost of random I/O exceeds a full-table scan, when a function wraps the indexed column, or when the query returns such a large fraction of rows that a sequential scan is cheaper.