Linear search
Not met yet
A linear search looks at each item in turn from the front and stops at the first match. It works on any list, sorted or not, and takes up to n looks, so it's O(n). The slowest search is for something that isn't there, because only after looking at everything can it say no: return -1 goes after the loop, not inside it. in, .index() and .count() are linear searches.
Try it
main.pyOutput
Press Run and what your program prints shows up here.
Easy to get wrong
- Thinks a linear search that returns on a match gives the last match rather than the first.
- Thinks searching for something that isn't there is quick, when it means looking at everything.
- Thinks a search can say "not there" as soon as one item doesn't match, so puts the not-found answer inside the loop.
- Thinks a linear search only works on a sorted list.