Linear search, the honest baseline

The worst case comes from a target that is missing, or one sitting at the very end.

Recall the rule from lesson 1-2: the worst case is the input that forces the most work. A miss makes the scan touch all n elements, and so does a hit at the last index.

The miss is the version to quote, because it is the only one guaranteed to cost n. A hit anywhere before the end costs less.

Keep that number in mind, because this unit is about beating it. Everything that follows buys its speed by refusing to look at most of the data.

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, and it is the correct choice surprisingly often.

• The data is unsorted and will only be searched once.
• You need every match rather than just one.
• The list is tiny, so nothing fancier can pay for its own setup.

That first case deserves emphasis. Sorting to enable a faster search costs O(n log n), so for a single search on unsorted data the O(n) scan wins outright, and the sort only pays off across many searches.

Python's in operator, list.index, max, and min are all linear searches underneath. Writing x in some_list is choosing an O(n) scan, and the point is to know that you chose it.

When every match is wanted

find_all collects every index where the value appears, which forces a full scan no matter what.

def find_all(nums, target):
    hits = []
    for i, n in enumerate(nums):
        if n == target:
            hits.append(i)
    return hits

readings = [3, 7, 3, 9, 3, 1]
print(find_all(readings, 3))
print(find_all(readings, 8))
print(7 in readings)

Output

[0, 2, 4]
[]
True

There is no early return here, and there cannot be. Finding one 3 says nothing about whether another appears later, so the loop has to reach the end of the list.

That makes this function O(n) in every case rather than only in the worst one. The best case and the worst case are the same, which is unusual and worth recognizing.

The empty result for 8 is a clean miss, and the third line is a reminder that in is running this same scan with the loop hidden.

Searching from the right

last_index finds the last occurrence by walking backwards.

def last_index(nums, target):
    for i in range(len(nums) - 1, -1, -1):
        if nums[i] == target:
            return i
    return -1

print(last_index([5, 2, 5, 8, 5, 1], 5))
print(last_index([5, 2, 5, 8, 5, 1], 9))

Output

4
-1

range(len(nums) - 1, -1, -1) counts down through len−1, len−2, and so on to 0. The middle −1 is the stopping bound, which has to be −1 rather than 0 for index 0 to be included.

Walking backwards is what turns a first-match search into a last-match search. The first match met from the right is the last occurrence overall, so no extra bookkeeping is needed.

The alternative would be a forward scan that records every hit and keeps the largest, which is also O(n) but does more work and cannot return early.

The miss still returns −1 after checking everything, so the worst case is unchanged by the direction of travel.

All 5,000 comparisons.

A linear scan can only rule out the elements it has actually looked at, so a definite miss costs n comparisons with no way around it.

This is the worst case from lesson 1-2, and the reason is worth stating precisely. Saying not found is a claim about the entire list, and the only evidence the scan has is what it has examined.

The next lesson gets the same answer in about 13 comparisons, on one condition: the list has to be sorted. Sorted data lets a search rule out half the list per comparison, which is what buys the drop from 5,000 to 13.