Simple search checks elements one at a time until it finds the target or reaches the end. It is easy to write, but it may inspect every element. section 1.9 section 1.3
Its trade-off becomes clearer as the list grows:
- The worst-case running time is O(n): a list of n elements may require checking all n elements. section 1.9 section 1.4
- The first element may produce an immediate answer, but Big O describes the worst case rather than that lucky result. section 1.9
- Simple search is easier to write and may introduce fewer bugs, while binary search grows much more slowly on large lists. section 1.7 section 1.12
A phone book and a guessing game
Searching for Adit in a phone book illustrates both outcomes: Adit might be first, or the search might scan every entry. Guessing numbers 1, 2, 3, and onward shows the same pattern; if the answer is 99, up to 99 guesses may be needed. section 1.9 section 1.3
Running time for simple search vs. binary search with a list of 100 elements
Compare the running time of simple search and binary search on a 100-element list. section 1.7
