Linear search and binary search explained

Linear search and binary search for GCSE Computer Science: how each works, why binary search needs sorted data, and how many steps each takes. Watch a robot search a row of numbered cards both ways, then try exam-style questions.

Guidefree, runs in your browser

A search algorithm finds an item in a list, or tells you it is not there. GCSE Computer Science asks you to know two of them. Linear search looks at every item in turn. Binary search looks at the middle item and throws away half of the list each time. Binary search is far faster on a big list, but it only works if the list is sorted.

On this page a small robot searches a row of 16 numbered cards on the mat. Each demo below is a real program you can change and run.

Each card is an AprilTag, a square code that the robot's camera can read as a number. The program does not know what is on the cards. To look at a card, the robot slides sideways until it stands in front of it, then reads the number with its camera. That is one comparison. It is the same as walking along a row of cards and turning each one over.

The camera sees several cards at once, so the program reads the one straight ahead: the tag nearest the middle of the picture. marker_tags() gives each tag in view as [number, x in the picture, y in the picture, distance], and the middle of the picture is at x = 160.

The idea in one line

linear search: look at each item in turn, from the start
binary search: look at the middle item, then throw away the half the target cannot be in

Linear search, step by step

1. Start at the first item.
2. If this item is the one you want, stop. You have found it.
3. If not, move on to the next item.
4. If you run out of items, stop. The item is not in the list.

The cards in this row are in no order at all. That does not matter to linear search.

from bugbot import *
connect()

# change TARGET and press Run
TARGET = 34

set_cv("apriltag")

def go_to(i):
    # slide sideways until the robot is in front of card i
    x, y = position()
    dx = 25 + 10 * i - (100 + x)
    if dx > 0.5:
        right(80, distance=dx)
    elif dx < -0.5:
        left(80, distance=-dx)

def read_card():
    # the number on the card straight ahead: the tag
    # nearest the middle of the picture (x = 160)
    best = None
    for tag in marker_tags():
        if best is None or abs(tag[1] - 160) < abs(best[1] - 160):
            best = tag
    return best[0]

checks = 0
found = -1
for i in range(16):
    go_to(i)
    number = read_card()
    checks = checks + 1
    plot("comparisons", checks)
    print("card", i, "reads", number)
    if number == TARGET:
        found = i
        break

if found >= 0:
    draw("found", [(25 + 10 * found, 60)], "green", "squares", 8)
    print("found", TARGET, "at card", found)
else:
    print(TARGET, "is not in the row")
print("comparisons:", checks)

The robot starts in the middle of the row, so it slides to card 0 first. Then it reads the cards one at a time. The chart counts comparisons: how many cards it has checked against the target. Each card adds one. When it finds the target, a green square marks the card.

Change TARGET and run it again.

• TARGET = 45: 45 is on card 0, so it takes 1 comparison. This is the best case.
• TARGET = 50: 50 is not in the row. The robot has to check all 16 cards before it can say so. This is the worst case, and so is a target on the last card.

For a list of n items, linear search makes 1 comparison at best and n at worst. If the item is there, it takes about n ÷ 2 on average.

Binary search, step by step

Binary search needs a sorted list. Here are the same 16 cards, sorted from smallest to largest.

1. Look at the middle item.
2. If it is the one you want, stop. You have found it.
3. If the target is smaller, throw away the middle item and everything after it.
4. If the target is bigger, throw away the middle item and everything before it.
5. Repeat with what is left, until you find it or nothing is left.

The program keeps two numbers. low is the first card still in the search, and high is the last. At the start, low is 0 and high is 15.

Finding the middle

The middle is mid = (low + high) // 2. In Python, // divides and rounds down to a whole number. In exam pseudocode the same thing is written (low + high) DIV 2.

With 16 cards there is no single middle card. (0 + 15) ÷ 2 is 7.5, which rounds down to 7. So the first card the robot looks at is card 7. This is the rule in our lessons, and it is the rule used on this page.

Some books round up instead. That also works, as long as you use the same rule every time. If an exam question tells you which rule to use, use that one. If it does not, round down, and keep to it.

from bugbot import *
connect()

# change TARGET and press Run
TARGET = 71

set_cv("apriltag")

def go_to(i):
    # slide sideways until the robot is in front of card i
    x, y = position()
    dx = 25 + 10 * i - (100 + x)
    if dx > 0.5:
        right(80, distance=dx)
    elif dx < -0.5:
        left(80, distance=-dx)

def read_card():
    # the number on the card straight ahead: the tag
    # nearest the middle of the picture (x = 160)
    best = None
    for tag in marker_tags():
        if best is None or abs(tag[1] - 160) < abs(best[1] - 160):
            best = tag
    return best[0]

def card_x(i):
    return 25 + 10 * i

low = 0
high = 15
checks = 0
found = -1
while low <= high:
    # the blue line: the cards still in the search
    draw("low to high", [(card_x(low) - 4, 60), (card_x(high) + 4, 60)],
         "blue", "line", 3)
    plot("low", low)
    plot("high", high)
    mid = (low + high) // 2        # round down
    go_to(mid)
    number = read_card()
    checks = checks + 1
    print("low", low, "high", high, "mid", mid, "reads", number)
    wait(1)
    if number == TARGET:
        found = mid
        break
    elif TARGET < number:
        high = mid - 1             # throw away mid and above
    else:
        low = mid + 1              # throw away mid and below

plot("low", low)
plot("high", high)
if found >= 0:
    draw("found", [(card_x(found), 60)], "green", "squares", 8)
    print("found", TARGET, "at card", found)
else:
    draw("low to high", [], "blue", "line", 3)
    print(TARGET, "is not in the row")
print("comparisons:", checks)

The blue line under the row runs from card low to card high: the cards still in the search. Each look moves low up past the middle or high down past the middle, so the blue line halves each time. On the chart, the two lines close in on each other. The search ends when it finds the card, or when low goes past high, because then no cards are left.

A worked trace

This is the binary search in the demo above, written as a trace table. It searches for 71 in the 16 sorted cards.

Look at the mid column. (8 + 15) ÷ 2 is 11.5, which rounds down to 11. (12 + 15) ÷ 2 is 13.5, which rounds down to 13. Four comparisons found the card. A linear search would have needed 13.

Now search for 40, which is not in the row. Set TARGET = 40 in the demo to check it.

In an exam, show every value of low, high and mid, and say which half you threw away each time. The trace tables guide shows how to lay one out.

Why binary search needs sorted data

Binary search throws away half the list after one comparison. That is only safe if every item before the middle is smaller, and every item after it is bigger. Here is the same binary search, run on the jumbled cards from the first demo.

from bugbot import *
connect()

# change TARGET and press Run
TARGET = 71

set_cv("apriltag")

def go_to(i):
    # slide sideways until the robot is in front of card i
    x, y = position()
    dx = 25 + 10 * i - (100 + x)
    if dx > 0.5:
        right(80, distance=dx)
    elif dx < -0.5:
        left(80, distance=-dx)

def read_card():
    # the number on the card straight ahead: the tag
    # nearest the middle of the picture (x = 160)
    best = None
    for tag in marker_tags():
        if best is None or abs(tag[1] - 160) < abs(best[1] - 160):
            best = tag
    return best[0]

def card_x(i):
    return 25 + 10 * i

low = 0
high = 15
checks = 0
found = -1
while low <= high:
    # the blue line: the cards still in the search
    draw("low to high", [(card_x(low) - 4, 60), (card_x(high) + 4, 60)],
         "blue", "line", 3)
    plot("low", low)
    plot("high", high)
    mid = (low + high) // 2        # round down
    go_to(mid)
    number = read_card()
    checks = checks + 1
    print("low", low, "high", high, "mid", mid, "reads", number)
    wait(1)
    if number == TARGET:
        found = mid
        break
    elif TARGET < number:
        high = mid - 1             # throw away mid and above
    else:
        low = mid + 1              # throw away mid and below

plot("low", low)
plot("high", high)
if found >= 0:
    draw("found", [(card_x(found), 60)], "green", "squares", 8)
    print("found", TARGET, "at card", found)
else:
    draw("low to high", [], "blue", "line", 3)
    print(TARGET, "is not in the row")
print("comparisons:", checks)

The robot reads card 7 and sees 39. 71 is bigger than 39, so it throws away cards 0 to 7. But 71 is on card 2, one of the cards it has just thrown away. From then on it cannot find it. It stops after 4 comparisons and says 71 is not there.

Binary search does not crash on an unsorted list. It gives a wrong answer and looks sure of itself, which is worse. Try TARGET = 45: it is on card 0, and binary search misses that too. Try TARGET = 39: it is found at once, but only by luck, because 39 happens to be on the middle card.

So before you can use binary search, the list has to be sorted, and kept sorted when new items are added. Sorting takes time. Our lessons on bubble sort and merge sort show how.

Counting comparisons

Each look at the middle halves what is left. So the question is: how many times can you halve the list before only one item is left?

16 halves to 8, then 4, then 2, then 1. That is 4 halvings. Then one more look checks the last card. So binary search needs at most 5 comparisons for 16 items. You saw this in the demo: TARGET = 92 takes 5.

The number of halvings is called log₂ n (say "log base 2 of n"). Worst cases, for the search on this page:

The rule is: take the whole number part of log₂ n, then add 1. Many books round this off and say binary search takes "about log₂ n" comparisons. For a big list the extra 1 makes little difference.

Look at what happens when the list doubles. Linear search needs twice as many comparisons. Binary search needs just one more, because one more look halves the bigger list back to the old size.

On this page, one comparison means one item looked at. A program may test == and then < on the same item, but that is still one item checked.

The race

Now both searches, one after the other, on the sorted cards. Each one starts with the robot in front of card 7. The chart counts the comparisons of each, and the console shows how far the robot drove and how long it took.

from bugbot import *
connect()

# change TARGET and press Run
TARGET = 84

set_cv("apriltag")

def go_to(i):
    # slide sideways until the robot is in front of card i
    x, y = position()
    dx = 25 + 10 * i - (100 + x)
    if dx > 0.5:
        right(80, distance=dx)
    elif dx < -0.5:
        left(80, distance=-dx)

def read_card():
    # the number on the card straight ahead: the tag
    # nearest the middle of the picture (x = 160)
    best = None
    for tag in marker_tags():
        if best is None or abs(tag[1] - 160) < abs(best[1] - 160):
            best = tag
    return best[0]

driven = 0
def look(i, name, checks):
    # drive to card i, read it, and count the drive
    global driven
    x, y = position()
    go_to(i)
    x2, y2 = position()
    driven = driven + abs(x2 - x)
    plot(name, checks)
    return read_card()

def linear():
    checks = 0
    for i in range(16):
        checks = checks + 1
        if look(i, "linear", checks) == TARGET:
            break
    return checks

def binary():
    low = 0
    high = 15
    checks = 0
    while low <= high:
        mid = (low + high) // 2
        checks = checks + 1
        number = look(mid, "binary", checks)
        if number == TARGET:
            break
        elif TARGET < number:
            high = mid - 1
        else:
            low = mid + 1
    return checks

# both start in front of card 7, in the middle
go_to(7)
start = clock()
checks = linear()
print("linear | comparisons", checks, "| cm", round(driven),
      "| seconds", round(clock() - start))

go_to(7)
driven = 0
start = clock()
checks = binary()
print("binary | comparisons", checks, "| cm", round(driven),
      "| seconds", round(clock() - start))

For a robot, every comparison costs a drive to the card and a look with the camera, so fewer comparisons means less driving. These are the results from this program for other targets:

Binary search never needed more than 5 comparisons. Linear search needed anything from 1 to 16. For 3, on the very first card, linear search won: 1 comparison and 6 seconds, against 4 comparisons and 8 seconds.

When linear search is the better choice

Binary search is faster on big sorted lists. Linear search is still the right choice when:

• The list is not sorted, and you only need to search it once. Sorting it first takes longer than one linear search.
• The list is short. With 10 items, the difference is a few comparisons.
• The items can only be read in order, one after another, such as records in a file or a list where each item points to the next. Binary search needs to jump straight to the middle.
• New items are added all the time. A sorted list has to be kept in order every time something is added.
• You want the simplest code. Linear search is short and hard to get wrong.

Binary search wins when the list is big, already sorted, and searched many times.

Linear and binary search in Python

The demos drive the robot to each card and read it with the camera. Without the robot, each search is a short function. Both return the index of the target, or -1 if it is not in the list. -1 can never be a real index, so it is a safe way to say "not found".

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

def binary_search(items, target):
    # items must be sorted
    low = 0
    high = len(items) - 1
    while low <= high:
        mid = (low + high) // 2
        if items[mid] == target:
            return mid
        elif target < items[mid]:
            high = mid - 1
        else:
            low = mid + 1
    return -1

cards = [3, 8, 12, 17, 21, 26, 34, 39,
         45, 52, 58, 63, 71, 77, 84, 92]
print(linear_search(cards, 71))
print(binary_search(cards, 71))
print(binary_search(cards, 40))

It prints 12, 12, then -1. The same binary search in exam-style pseudocode:

low = 0
high = items.length - 1
found = -1
WHILE low <= high AND found == -1
    mid = (low + high) DIV 2
    IF items[mid] == target THEN
        found = mid
    ELSEIF target < items[mid] THEN
        high = mid - 1
    ELSE
        low = mid + 1
    ENDIF
ENDWHILE
OUTPUT found

Practice questions

Try each one on paper before you look at the answers below. Lists start at index 0. For a binary search, find the middle with (low + high) DIV 2, which rounds down.

Question 1: linear search (3 marks)

A robot records the ID of each marker it sees:

ids = [14, 3, 27, 9, 31, 6]

a) A linear search looks for 9. List the items it compares with 9, in order. (1 mark)

b) How many comparisons does a linear search make to find out that 20 is not in the list? (1 mark)

c) State why a binary search cannot be used on this list. (1 mark)

Question 2: tracing a binary search (3 marks)

A sorted list of distances, in cm:

d = [2, 5, 9, 14, 20, 26, 33, 40, 47, 55, 61]

Show the steps a binary search takes to find 14. For each step, give low, high, mid and the item at mid.

Question 3: a target that is not there (3 marks)

Using the same list as Question 2, show the steps a binary search takes when it searches for 60. Explain how the algorithm knows that 60 is not in the list.

Question 4: the wrong list (3 marks)

A student runs a binary search for 9 on the list from Question 1, [14, 3, 27, 9, 31, 6]. Show the items it compares with 9, state what it outputs, and explain why.

Question 5: counting comparisons (3 marks)

A sorted list holds 500 names.

a) What is the largest number of comparisons a linear search could make? (1 mark)

b) What is the largest number of comparisons a binary search could make? (1 mark)

c) The list grows to 1,000 names. How many comparisons could a binary search need now? (1 mark)

Question 6: choosing a search (4 marks)

A robot adds a new temperature reading to the end of a list every second. Once a day, a program searches the whole list for any reading above 90 °C. A student says the program should use binary search, because it is faster. Explain whether the student is right.

Answers

Question 1.

a) 14, 3, 27, 9 (1 mark).

b) 6 (1 mark). Every item must be checked before the search can say 20 is not there.

c) The list is not sorted (1 mark).

Question 2. 3 comparisons. 1 mark for each correct row, including the correct mid.

(3 + 4) DIV 2 is 3, because 3.5 rounds down.

Question 3.

• Items compared: 26, 47, 55, 61 (1 mark).
• Correct values of low, high and mid at each step (1 mark).
• It stops when low (10) is greater than high (9), so no items are left to search, and 60 was not found (1 mark).

Question 4.

• It compares 27 (mid = 2), then 14 (mid = 0) (1 mark). 9 < 27, so high = 1. 9 < 14, so high = -1. Now low > high.
• It outputs that 9 is not in the list, even though 9 is at index 3 (1 mark).
• The list is not sorted. When 9 < 27, the search throws away everything after 27, which assumes the items after 27 are all bigger. 9 is one of them (1 mark).

Question 5.

a) 500 (1 mark).

b) 9 (1 mark). 500 can be halved 8 times before only 1 is left (250, 125, 62, 31, 15, 7, 3, 1), then 1 more look checks the last item. Or: 2⁸ = 256 and 2⁹ = 512, so log₂ 500 is between 8 and 9. The whole number part is 8, plus 1 is 9.

c) 10 (1 mark). Doubling the list adds only one comparison.

Question 6. The student is not right. Up to 4 marks from:

• The list is not sorted. It is in the order the readings were taken, so binary search would give wrong answers (1 mark).
• To use binary search the list would have to be sorted first, and a sort takes longer than one linear search (1 mark).
• The list is only searched once a day, so the time saved by a faster search is small (1 mark).
• Binary search finds one exact value. This program wants every reading above 90, so it has to look at every item anyway, which is a linear search (1 mark).
• A linear search is the better choice here (1 mark, only with a reason).

Questions

What is the difference between linear search and binary search?

Linear search checks each item in turn, from the start, until it finds the target or runs out of items. It works on any list. Binary search looks at the middle item of a sorted list, then throws away the half the target cannot be in, and repeats. It needs far fewer comparisons on a big list, but the list must be sorted.

How does a linear search work?

Start at the first item. If it is the target, stop. If not, move to the next item. Keep going until you find the target or reach the end of the list. If you reach the end, the target is not in the list.

How does a binary search work?

Look at the middle item of a sorted list. If it is the target, stop. If the target is smaller, throw away the middle item and everything after it. If it is bigger, throw away the middle item and everything before it. Repeat with the part that is left, until you find the target or nothing is left.

Why does binary search need the data to be sorted?

Because it decides which half to throw away from one comparison. That is only safe if every item before the middle is smaller and every item after it is bigger. On an unsorted list it can throw away the half that holds the target, and then wrongly say the target is not there. The third demo on this page shows this happening.

How do you find the middle item in a binary search?

Add the first and last positions still in the search, and divide by 2: mid = (low + high) DIV 2, which is (low + high) // 2 in Python. If the answer has a half, round it down. With 16 items, positions 0 to 15, the first middle is (0 + 15) ÷ 2 = 7.5, so position 7. If a question gives you a different rule, use the question's rule, and use it every time.

Which is faster, linear search or binary search?

On a large sorted list, binary search. For 1,000 items, linear search could need 1,000 comparisons and binary search at most 10. On a short list, or when the target is near the start, linear search can be just as quick or quicker. In the race on this page, linear search won when the target was on the first card.

How many comparisons does a binary search need?

At most the whole number part of log₂ n, plus 1, for a list of n items. That is 4 for 8 items, 5 for 16, 10 for 1,000 and 20 for a million. Each time the list doubles in size, binary search needs one more comparison.

When would you use a linear search instead of a binary search?

When the list is not sorted and you only search it once, when the list is short, when the items can only be read one after another, or when new items are added so often that keeping the list sorted is not worth it. Linear search is also simpler to write.

What are the advantages and disadvantages of linear search?

Advantages: it works on unsorted data, and it is simple to write. Disadvantages: it is slow on a big list, because in the worst case it checks every item.

What are the advantages and disadvantages of binary search?

Advantage: it is much faster on a big list, because each comparison halves the items left to search. Disadvantages: the list must be sorted first, and kept sorted, and the code is harder to get right than a linear search.

Are linear search and binary search on the GCSE Computer Science specification?

Yes, on all three main boards. OCR J277 covers them in searching and sorting algorithms (2.1.3). AQA 8525 asks you to explain and compare them (3.1.3). Pearson Edexcel 1CP2 lists them among the standard algorithms (1.2.6). Our GCSE lessons F5.5 Linear search and F5.6 Binary search teach them with the robot, and A5.3 Linear and binary search takes them on to A level, with recursion and time complexity.

Learn it step by step

These lessons build the same ideas one at a time, each with tasks the simulator marks.

1. F5.5 Linear search Algorithms, GCSE
2. F5.6 Binary search Algorithms, GCSE
3. A5.3 Linear and binary search Algorithms and complexity, A level