- Target
- Compared
- Ruled out
- Found
Linear search
Linear search is the simplest way to find a value: start at the beginning and check every value in turn until it turns up. It works on any list, sorted or not. Choose the value to look for, play the search or step through it one comparison at a time, and watch how the cost depends on where the value is, or whether it is there at all. Press Play to watch the search, or Step and Back to go one comparison at a time. Drag the step slider to jump anywhere. The dashed line marks the value you search for. Choose the value, how many bars, how they start, or type your own numbers. Turn off Stop at the first match to find every match. With the board selected, the arrow keys step, the space bar plays and pauses, and Home and End jump to the start and the end.
How it works
- Choose the value to search for, and how many bars and how they start. Or type your own numbers.
- Press Play, or use Step and Back to move one comparison at a time. Drag the step slider to jump anywhere in the search.
- Turn off Stop at the first match to check every value and find all the matches.
How linear search works
Compare the first value with the target. If they are equal, you are done. If not, move on to the second value, then the third, and so on. If you reach the end of the list without a match, the target is not in the list. There is nothing to prepare: the list does not need to be sorted.
How many comparisons
A value at place k is found after k comparisons. The best case is one comparison, when the target is first. The worst case is n, when it is last or missing, because only after checking every value can you be sure it is not there. On average, for a value that is in the list, it takes about (n + 1)/2. For a sorted list, binary search does far better: about log₂ n comparisons, 6 instead of up to 40 for 40 values.
Frequently asked questions
How does linear search work?
It checks the values of a list one by one, from the first to the last, until it finds the target or runs out of values. It is also called sequential search.
What is the time complexity of linear search?
O(n): in the worst case, when the target is last or missing, it compares the target with all n values. On average, for a target that is in the list, it takes about (n + 1)/2 comparisons.
When is linear search a good choice?
For short lists, for lists that are not sorted and are searched only once or twice, and for data you can only read in order, such as a stream. Sorting first so that binary search can be used only pays off if you search many times.
Why does a missing value cost the most?
Because nothing tells linear search to stop early. A match can only be ruled out by checking every value, so a value that is not in the list always takes n comparisons.
Are my numbers sent anywhere?
No. The search runs in your browser, and your last settings stay in this browser's local storage.
Ready to try it?
Open PictorX in your browser — no install, no credit card required to start.
Go to Editor