Linear search

Code in:JavaC#PythonJavaScript

In short: Linear search checks the elements one by one until it finds the one it wants or reaches the end: O(n) comparisons, and it works on an unsorted list.

Problem

The warehouse scanner

In the warehouse the products are recorded in a list in the order they arrived: flour from Monday, sugar from Tuesday, oil, rice. A worker scans a box, and the program must find the product by its barcode:

shelf = [
    Product("3800200101112", "Flour"),
    Product("3800200104403", "Sugar"),
    Product("3800200107251", "Oil"),
    Product("3800200102690", "Rice"),
    Product("3800200109958", "Salt"),
    Product("3800200105837", "Coffee"),
]

The barcodes are not sorted. You cannot open the list in the middle and say "the rice is further on": the next barcode can be anything. How do you find the product, and what does it cost when there are 50 000 products and 2000 scans a day?

The idea

You look at every box

Since the order does not help, one thing is left: you start at the first box and compare its barcode with the one you look for. If it matches, you are done: you return the place. If not, you move to the next one. If the boxes run out, the product is not there.

This is linear search: you go through the elements one by one until you find the one you look for or reach the end. It returns the place (the index) or a sign for "not there": None.

See it

The pointer on the shelf

def find(shelf, barcode):
    for i, product in enumerate(shelf):
        if product.barcode == barcode:
            return i
    return None

rice = find(shelf, "3800200102690")
print("3800200102690 ->", rice, shelf[rice].name)
print("3800200100000 ->", find(shelf, "3800200100000"))

Output

3800200102690 -> 3 Rice
3800200100000 -> None

def find(shelf, barcode):
    for i, product in enumerate(shelf):
        if product.barcode == barcode:
            return i
    return None


rice = find(shelf, "3800200102690")
missing = find(shelf, "3800200100000")

Step by step, in words

1. The scanner reads the barcode of the rice: 3800200102690. find starts at the first box.
2. It compares the barcode of every box with the one it looks for: flour, sugar, oil. No match.
3. The fourth box is the rice. return 3: found after 4 comparisons.
4. A barcode the warehouse does not have: 3800200100000. find starts from the beginning again.
5. The pointer passes every box, and none matches.
6. The boxes run out: return None after 6 comparisons. A missing product is the worst case: n comparisons for n boxes.

The rice is found after 4 comparisons. The missing barcode goes through all 6 boxes: that is the only way to say it is not there.

In Python -1 is a real index: shelf[-1] is the last product. If find returned -1, code like shelf[find(shelf, code)].name would give the coffee for a barcode that is not there, with no error at all. That is why "not there" is None, and shelf[None] stops at once with a TypeError.

Try it

Fill in

What does find return when the boxes run out?

def find(shelf, barcode):
    for i, product in enumerate(shelf):
        if product.barcode == barcode:
            return i
    return 

Check

The idea

How many comparisons

The number of comparisons depends on where the product is:

• the best case: the first box, 1 comparison;
• the worst case: the last box or a product that is not there, n comparisons;
• the usual case: if every place is equally likely, about n/2 on average.

The worst and the usual case grow with n, so linear search is O(n). The program counts:

def comparisons(shelf, barcode):
    count = 0
    for product in shelf:
        count += 1
        if product.barcode == barcode:
            return count
    return count

print("Flour:", comparisons(shelf, "3800200101112"))
print("Rice:", comparisons(shelf, "3800200102690"))
print("Missing:", comparisons(shelf, "3800200100000"))

Output

Flour: 1
Rice: 4
Missing: 6

Run the two extreme cases on a big warehouse. We count one comparison per box:

• The barcode is missing (worst case) O(n)
• The first product (best case) O(1)

Algorithm	n = 10	n = 1,000	n = 100,000
The barcode is missing (worst case)	10	1,000	100,000
The first product (best case)	1	1	1

The code runs in your browser, in JavaScript. The number of operations is the same in every language, because the algorithm is the same. The time depends on the machine, so it is only for comparison. “≈” is an estimate from the curve: we do not run an n that big, so the page does not freeze.

The first box costs 1 comparison for every n: O(1). A missing product costs n: with 100 000 products that is 100 000 comparisons. The memory is O(1): one index.

Try it

Predict the output

The salt is the fifth box on the shelf. How many comparisons does the search make?

def comparisons(shelf, barcode):
    count = 0
    for product in shelf:
        count += 1
        if product.barcode == barcode:
            return count
    return count


print("Salt:", comparisons(shelf, "3800200109958"))

Answer

Salt: 5

Salt: 6

Salt: 4

Check

See it

The built-ins search the same way

Every language has a ready search in a list. Inside it is the same loop:

barcodes = [
    "3800200101112", "3800200104403", "3800200107251",
    "3800200102690", "3800200109958", "3800200105837",
]
print(barcodes.index("3800200102690"))
print("3800200100000" in barcodes)
try:
    barcodes.index("3800200100000")
except ValueError as e:
    print("ValueError:", e)

Output

3
False
ValueError: '3800200100000' is not in list

index returns the place, and if it is not there, it raises ValueError. in gives only True or False. Both go from the first element on: O(n). So if code in barcodes: barcodes.index(code) searches twice.

One call looks like one operation, but inside there are up to n comparisons. The built-in function is faster than your loop by some constant factor, not by an order.

Try it

Find the bug

A colleague wrote the search like this. The flour is found, and the rice "is not there":

def find(shelf, barcode):
    for i, product in enumerate(shelf):
        if product.barcode == barcode:
            return i
        else:
            return None
    return None

print(find(shelf, "3800200101112"))
print(find(shelf, "3800200102690"))

Output

0
None

Which line is the bug on?

Pick the line with the bug.

1def find(shelf, barcode):2 for i, product in enumerate(shelf):3 if product.barcode == barcode:4 return i5 else:6 return None7 return None

Check

The idea

When it is right and when it is not

Linear search is the right choice when:

• there are few products: ten or a hundred comparisons are not noticeable;
• you search once: every faster way first needs at least n steps to prepare;
• the data is unsorted or keeps changing, and there is nothing to maintain.

It is not when there are many searches. 2000 scans a day in 50 000 products are up to 100 000 000 comparisons. Then you prepare the data once:

• a table barcode → product (dict): 50 000 steps once, and after that every search is O(1) on average;
• a sorted list and binary search: sorting is O(n log n) once, and every search after it is O(log n), about 16 comparisons for 50 000.

by_barcode = {product.barcode: product for product in shelf}
print(by_barcode["3800200102690"].name)
print(by_barcode.get("3800200100000"))

Output

Rice
None

The table costs memory: another n places. It is the same trade of time for memory as the set in the lesson "Space complexity".

Exercise

All the boxes of one product

Solve the task in your editor.

Stocktaking. One product may have come with several deliveries and be in several places in the list. Write find_all(shelf, barcode), which returns all places of the barcode, not just the first one. The shelf is as above, plus more rice and more salt at the end (places 6 and 7).

Output

Rice: 3, 6
Salt: 4, 7

More tasks

• The last place. Return the last place of the barcode. Where is it better to start?
• By name, ignoring case. Find the product by name ("rice" and "Rice" are the same). How many comparisons are there in the worst case?
• Products under the minimum. List all products with fewer than 10 items in stock. Can you stop before the end?

Test

Check yourself

1. The list has 10 000 unsorted products. How many comparisons does linear search make for a product that is not there?

10 0001About 14

2. The product is there, and every place is equally likely. How many comparisons are needed on average for n products?

About n/2Always nAbout log n

3. Why does find not return 0 when the product is not there?

It may return 0, it makes no differenceBecause 0 is an errorBecause 0 is a real place: the first box

4. The scanner makes 2000 searches a day in 50 000 products. Which is better?

Linear search every timeA new list for every searchA table barcode → product, made once

5. When is linear search the right choice?

Always, when there is a lot of dataWhen you search once in a small or unsorted listOnly when the list is sorted

Check

Start the lesson over

Related lessons

• Builds on: Time complexity: counting steps · Big-O: how the work grows · Best, average and worst case · Space complexity
• Continues in: Binary search · Binary search on the answer · Trie · Prefix sums
• Tasks on this topic: Searching