Linear Search

Linear Search

Step 1 of 7

targetgraychecks0

i

red

blue

green

teal

gray

pink

012345

Linear search needs no order and no setup — it just looks at everything until it finds gray.

The Idea

Check items one at a time until you find the target or run out of items. It needs no ordering and no preparation at all. The worst case is O(n), and for small or unsorted data that is genuinely the right choice.

Real-World Example

Waiting at the baggage carousel, you inspect each bag as it rolls past. The bags arrive in no useful order, so there is nothing smarter to do than look at every one until yours appears.

The Code

def linear_search(items, target):
    for i, item in enumerate(items):
        # check one at a time, in order
        if item == target:
            return i          # found it: return the index
    return -1                 # not here

print(linear_search(["red", "blue", "green"], "green"))   # 2
print(linear_search(["red", "blue", "green"], "pink"))    # -1

Your turn

Put the steps in the right order.

1. 1Return -1 because nothing matched↑↓
2. 2Compare the current item to the target↑↓
3. 3Start at index 0↑↓
4. 4Move to the next index when there is no match↑↓

Check order

Mini quiz

1 / 3

Worst-case comparisons for a linear search over n items?

• A1
• Blog n
• Cn
• Dn²