Quiz
Warm-up from lesson 1-2: linear search is O(n) in the worst case. Which input causes that worst case?
Linear search, the honest baseline
Linear search means checking elements one by one, left to right, until you find what you want. You already wrote one in lesson 1-2.
It sounds too simple to matter, but it is the correct choice surprisingly often:
- The data is unsorted and you will only search it once.
- You need every match, not just one.
- The list is tiny, so nothing fancier can pay off.
Python's in operator (7 in nums), list.index, max, and min are all linear searches under the hood. When you write x in some_list you are choosing an O(n) scan, and it is worth knowing that you chose it.
Code exercise · python
Run this. find_all collects every index where the value appears, which forces a full O(n) scan no matter what.
Code exercise · python
Your turn. Write last_index(nums, target): the index of the LAST occurrence of target, or -1. Scan from the right end so you can stop at the first hit you meet.
Problem
An unsorted list has 5,000 items and the value you want is not in it. How many comparisons does linear search make before it can say "not found"?