A topic in the Open Knowledge Graph — a free, open map of 15,495 topics and the order to learn them in.
Linear search (also called sequential search) finds a target value in a list by checking the elements one at a time, in order, until it finds a match or reaches the end. It returns the position of the first match, or a signal such as -1 when the target is absent. It works on any list, sorted or not. For a list of n elements it makes at most n comparisons, so its worst-case running time is O(n).
Act it out with a row of face-down cards: turn them over one by one and count the flips needed for different targets, including one that is missing. Then write the loop and trace it on a target at the front, in the middle, at the end, and absent. Count comparisons for each case before introducing big-O, and finally compare the counts with binary search on a sorted list of the same size.
Searching is one of the most common jobs a program does: find a name in a contact list, a product in an inventory, a word in a document. The simplest method is the one you would use with a messy stack of papers. Look at the first one. If it is not what you want, look at the next. Keep going until you find it or run out.
In code, linear search is a single loop:
```python
def linear_search(items, target):
for i in range(len(items)):
if items[i] == target:
return i
return -1
```
Notice where `return -1` sits. It is after the loop, not inside it. The function can say "not found" only after every element has been checked. Putting the "not found" return in an `else` branch inside the loop is one of the most common beginner bugs, because it makes the function give up after the first element.
How much work does it do? Count comparisons. If the target is first, one comparison. If it is last, or not present, every element is compared, so n comparisons for a list of n items. If the target is equally likely to be anywhere in the list, the average is about (n + 1) / 2. Computer scientists usually describe the worst case, so linear search is O(n): doubling the list roughly doubles the worst-case time.
Linear search has real strengths. It works on unsorted data. It works on structures you can only walk through in order, such as linked lists or a file being read line by line. It is short and hard to get wrong once the return is placed correctly. It also adapts easily: you can search for the largest value, for the first item meeting a condition, or for every match by collecting indexes instead of returning early.
Its weakness appears with large data searched often. A million-element list can require a million comparisons per search. If the list is sorted, binary search can find any item in about 20 comparisons by repeatedly halving the range. Sorting has its own cost, so the right choice depends on how often you search. For one search of unsorted data, linear search is the better choice. For many searches of the same data, sorting once and then using binary search is usually worth it.