Tracing a binary search

Name:

Date:

Class:

Quick Questions

Shade in the A or B circle for each question.

1. List: [3, 8, 12, 15, 21, 27, 34] (indexes 1 to 7). With low = 1 and high = 7, what is the first mid?

A mid = 3, because (1 + 7) DIV 2 = 3

B mid = 4, because (1 + 7) DIV 2 = 4

2. Searching for 21 in the same list: mid = 4 and list[4] = 15. What does the next row of the trace table show?

A high becomes 3, because 21 is greater than 15

B low becomes 5, because 21 is greater than 15

3. Searching for 21: low = 5 and high = 7. What is mid for this row?

A mid = 6, because (5 + 7) DIV 2 = 6

B mid = 5, because (5 + 7) DIV 2 = 5

4. The range is low = 1 and high = 6. What is mid?

A mid = 3, because 7 DIV 2 drops the .5

B mid = 4, because 7 DIV 2 rounds up

5. Searching for 10 in [3, 8, 12, 15, 21, 27, 34]: mid = 2 and list[2] = 8. What happens to low and high?

A low ← mid + 1, so low = 3

B high ← mid - 1, so high = 1

Match the Pairs

Draw a line connecting each item on the left to its match on the right.

Left column		Right column
1mid ← (low + high) DIV 2		AIF list[mid] < target THEN low ← mid + 1
2low > high		BFinds the middle index of the current search range, rounding down to a whole number
3The target is greater than the middle item, so the search moves to the upper half of the range		CIF list[mid] > target THEN high ← mid - 1
4The target is smaller than the middle item, so the search moves to the lower half of the range		DThe range is empty, so the target is not in the list and the search stops
5IF list[mid] < target THEN low ← mid		ELow should be set to mid + 1, not mid. Mid has already been checked, so the range may never shrink and the trace table repeats forever.
6Start: low ← 1, high ← 8, mid ← 4. Trace stops when low = high		FThe search should stop when low is greater than high, not when they are equal. When low equals high there is still one item left to check.

Definitions

mid ← (low + high) DIV 2

Fill in the Blanks

Complete each line of code by filling in the missing parts.

mid ← (low + high) ___ 2

WHILE low _ high mid ← (low + high) DIV 2

IF list[mid] < target THEN low ← _______

ELSE IF list[mid] > target THEN ____ ← mid - 1

IF low _ high THEN OUTPUT "Not found"

Spot the Error

Shade in the letter of the line that contains an error.

Question 1

A n ← 9

B low ← 0

C high ← n

D mid ← (low + high) DIV 2

Question 2

A low ← 1

B high ← 9

C mid ← (low - high) DIV 2

D OUTPUT mid

Question 3

A WHILE low ≤ high

B mid ← (low + high) DIV 2

C IF mid = target THEN

D found ← TRUE

Question 4

A WHILE low > high

B mid ← (low + high) DIV 2

C OUTPUT low, mid, high

D ENDWHILE

Question 5

A IF list[mid] > target THEN

B high ← mid + 1

C ELSE

D low ← mid + 1

Answer Key

Tracing a binary search

Section A: Quick Questions

B — mid = 4, because (1 + 7) DIV 2 = 4

B — low becomes 5, because 21 is greater than 15

A — mid = 6, because (5 + 7) DIV 2 = 6

A — mid = 3, because 7 DIV 2 drops the .5

A — low ← mid + 1, so low = 3

Section B: Match the Pairs

mid ← (low + high) DIV 2 → Finds the middle index of the current search range, rounding down to a whole number

low > high → The range is empty, so the target is not in the list and the search stops

The target is greater than the middle item, so the search moves to the upper half of the range → IF list[mid] < target THEN low ← mid + 1

The target is smaller than the middle item, so the search moves to the lower half of the range → IF list[mid] > target THEN high ← mid - 1

IF list[mid] < target THEN low ← mid → Low should be set to mid + 1, not mid. Mid has already been checked, so the range may never shrink and the trace table repeats forever.

Start: low ← 1, high ← 8, mid ← 4. Trace stops when low = high → The search should stop when low is greater than high, not when they are equal. When low equals high there is still one item left to check.

Section C: Definitions

mid ← (low + high) DIV 2 — Each row of a binary search trace table updates low, high and mid. The range halves each step until the target is found or low becomes greater than high.

Section D: Fill in the Blanks

mid ← (low + high) DIV 2

WHILE low ≤ high
    mid ← (low + high) DIV 2

IF list[mid] < target THEN
    low ← mid + 1

ELSE IF list[mid] > target THEN
    high ← mid - 1

IF low > high THEN
    OUTPUT "Not found"

Section E: Spot the Error

B — Pseudocode lists start at index 1, so the first row of the trace table must have low ← 1. Starting at 0 gives the wrong first mid (4 instead of 5).

C — The middle index is found by adding low and high, then using DIV 2. Subtracting gives a negative number, not the middle. It should be mid ← (low + high) DIV 2.

C — mid is an index, not a value in the list. The algorithm must compare the item list[mid] with the target, so the line should be IF list[mid] = target THEN.

A — The loop keeps going while the range is valid, which means low ≤ high. With low > high the loop would never start, so no trace rows would be produced.

B — If list[mid] is bigger than the target, the target is in the lower half. mid has been checked, so the new high must be mid - 1, not mid + 1.