Walking the whole list
Linear search scans elements one at a time from the start until it finds the target or runs off the end. It makes no assumptions: the data can be in any order, stored in any structure you can iterate.
When it shines
- The collection is unsorted, so cleverer methods cannot apply.
- The collection is tiny, where setup cost of fancy structures outweighs the gain.
- You only search once, so building an index or sorting first would never pay off.
Cost and behaviour
- In the worst case you touch every element, so the work grows in direct proportion to the size of the list.
- On average you find a present target after scanning about half the elements.
- A sentinel trick, placing the target at the very end, lets you drop the bounds check from the loop and run a little faster.
Linear search is also the fallback inside many libraries: once a sorted range gets small enough, switching to a plain scan beats the overhead of dividing further.
Key idea
Linear search trades speed for total flexibility: it works on any order at the price of scanning, on average, half the list.