Lesson 7.7

Trace binary search and count comparisons

Part 7: AlgorithmsReading, about 7 min1 exercise in this lesson

Tracing a binary search, and counting its comparisons

By the end of this you will be able to trace a binary search on a sorted list, row by row, count how many values it looks at, and work out the most it could ever need for a list of n values.

How it is asked

A binary search trace is a trace table with three columns that matter: low, high and mid. There are no past papers for the new course yet, but expect a part that counts as well:

Copy and complete the trace table for a given sorted list and target.
State how many comparisons the search made, or which values it looked at.
State the greatest number of comparisons it could make for a list of a given size.

Trace tables on past IB papers were marked by rows (or columns), as the lesson on tracing a loop showed, and our rubrics do the same. One wrong mid early on throws off every row after it, so the first row is the one to get right.

Key idea: Work out mid from low and high as they are now, round it down, and move past it.

Watch the three indexes

Here the target is not in the list, so the search runs until there is nothing left. Watch low and high close in, and mid jump between them.

Step through it

values = [5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55]

target = 42

low = 0

high = 10

looks = 0

while low <= high:

mid = (low + high) // 2

looks = looks + 1

if values[mid] == target:

break

elif values[mid] < target:

low = mid + 1

else:

high = mid - 1

print(looks)

Variables

Nothing yet. Press Next to run the first line.

Nothing has run yet.

Output

(nothing printed)

0/31

Looks at 30, 45, 35, 40, then stops. Four of the eleven values.

The search ends because low has passed high, not because low and high are equal. When they are equal there is still one value in range, and it gets looked at: here, the 40.

Quick check

In that search, after the look at 35, low and high are both 7. What happens next?

How it is marked

An exam-style question of our own, as a trace table with one row per look, and a last row for the check that stops the loop. Each row is a mark. The second script rounds the first middle up.

How it is marked

values is [2, 7, 11, 16, 20, 24, 29, 33] and target is 26. Copy and complete the trace table for the binary search above, one row for each value of mid and a last row for when the loop stops. [4]

[4]

lowhighmidvalues[mid]mark

low: 0, high: 7, mid: 3, values[mid]: 16. Mark [1].
(0 + 7) // 2 is 3, rounded down from 3.5. 16 < 26, so low moves to 4.

So far 1 of 4

The slip script scores 1 of 4. One rounding slip in row one, and the next two rows are wrong too.

Quick check

How many comparisons did that search make, counting one for each value of mid?

What counts as a comparison

In this course we count one comparison for each value of mid: each time the search looks at a value and compares it with the target. That is the count that grows as log n. In the code, one look can run two tests (== and then <), so if a question counts those separately it will say so. When you write a count in an answer, say what you counted: "3 values were looked at: 16, 24 and 29."

The most it can take

Each look removes the middle value and one side. The side that is left is at most half of what there was, rounded down. So the greatest number of looks for n values is how many times you can halve n, rounding down each time, before you reach 0:

7 values: 7, 3, 1, then 0. At most 3 looks.
8 values: 8, 4, 2, 1, then 0. At most 4 looks.
1000 values: at most 10. A million: at most 20.

That is why a binary search is O(log n): doubling n adds one more halving, so one more look.

Quick check

What is the greatest number of comparisons a binary search can make on a sorted list of 31 values?

Now try it yourself on the questions below.

Exercise 7.7.1 · Trace itTrace: binary search

Complete the trace table for this Python code. The values are sorted, so this is a binary search. // divides and throws away the remainder. Then answer the question below the table. [4]

Line 1: values = [4, 9, 13, 18, 25, 31, 40, 47]1values = [4, 9, 13, 18, 25, 31, 40, 47]
Line 2: target = 132target = 13
Line 3: low = 03low = 0
Line 4: high = 74high = 7
Line 5: found = False5found = False
Line 6: while low <= high and not found:6while low <= high and not found:
Line 7, indented 1 level: mid = (low + high) // 27    mid = (low + high) // 2
Line 8, indented 1 level: if values[mid] == target:8    if values[mid] == target:
Line 9, indented 2 levels: found = True9        found = True
Line 10, indented 1 level: elif values[mid] < target:10    elif values[mid] < target:
Line 11, indented 2 levels: low = mid + 111        low = mid + 1
Line 12, indented 1 level: else:12    else:
Line 13, indented 2 levels: high = mid - 113        high = mid - 1
Line 14: print(mid)14print(mid)

Fill in one row each time a line changes low, high, mid or found, or prints something. The table already has the right number of rows. In each row, write only what that line changes; you can leave the other cells empty or copy their values down. Write values the way Python shows them: 3 and 3.0 are different, and text goes in quotes. In the output column, write exactly what appears on screen, with no quotes around it.

Row	low	high	mid	found	output
1
2
3
4
5
6
7
8
9
10

How many values in the list were looked at, one for each value of mid?

Exercise 7.7.1 · Trace itTrace: binary search missing (Java)

Complete the trace table for this Java code. The array is sorted, so this is a binary search for a value that is not in it. Dividing two int values in Java throws away the remainder. Then answer the question below the table. [3]

Line 1: int[] values = {6, 11, 15, 22, 28, 35, 41};1int[] values = {6, 11, 15, 22, 28, 35, 41};
Line 2: int target = 30;2int target = 30;
Line 3: int low = 0;3int low = 0;
Line 4: int high = values.length - 1;4int high = values.length - 1;
Line 5: boolean found = false;5boolean found = false;
Line 6: while (low <= high && !found) {6while (low <= high && !found) {
Line 7, indented 1 level: int mid = (low + high) / 2;7    int mid = (low + high) / 2;
Line 8, indented 1 level: if (values[mid] == target) {8    if (values[mid] == target) {
Line 9, indented 2 levels: found = true;9        found = true;
Line 10, indented 1 level: } else if (values[mid] < target) {10    } else if (values[mid] < target) {
Line 11, indented 2 levels: low = mid + 1;11        low = mid + 1;
Line 12, indented 1 level: } else {12    } else {
Line 13, indented 2 levels: high = mid - 1;13        high = mid - 1;
Line 14, indented 1 level: }14    }
Line 15: }15}

Fill in one row each time a line changes low, high or mid. The table already has the right number of rows. In each row, write only what that line changes; you can leave the other cells empty or copy their values down. Write values the way Java shows them: 3 and 3.0 are different, and text goes in quotes.

Row	low	high	mid
1
2
3
4
5
6
7
8

How many values in the array were looked at before the loop stopped?

Report a problem with this page