Worst-case comparisons: linear versus binary search

Name:

Date:

Class:

Quick Questions

Shade in the A or B circle for each question.

1. A list has 1000 items. What is the worst-case number of comparisons for a linear search?

A About 10 comparisons

B Up to 1000 comparisons

2. A sorted list has 1000 items. About how many comparisons does a binary search need in the worst case?

A About 10 comparisons

B About 500 comparisons

3. Which statement describes why binary search is so much faster on large lists?

A It checks two items at a time instead of one

B It halves the remaining range after every comparison

4. Which gives the approximate worst-case comparisons for binary search on n items?

A log2 n

B n

5. A list is NOT sorted. Which search can you use to find a target correctly?

A Linear search

B Binary search

Match the Pairs

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

Left column		Right column
1comparisons = n		AWorst case for a linear search: the target is the last item or missing, so all n items are checked (1000 items means up to 1000 comparisons).
2comparisons ≈ log2 n		BWorst case for a binary search: each comparison halves the range, so 1000 sorted items need only about 10 comparisons.
3Binary search halves the remaining range each time, so it needs far fewer comparisons than linear search on a big sorted list.		CAbout 10 comparisons is the binary search figure. A linear search may need up to 1000 comparisons (n) in the worst case.
4Binary search only works on sorted data, so sorting first adds a cost that linear search does not have.		DBinary search does not check half of the items. It halves the range again and again, so it needs only about 10 comparisons (log2 1000).
5A linear search of 1000 items needs about 10 comparisons in the worst case.		EIF list[middle] < target THEN low ← middle + 1
6Binary search needs 500 comparisons for 1000 sorted items because it checks half of them.		Fmiddle ← (low + high) DIV 2

Definitions

log2 n

Fill in the Blanks

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

worstLinear ← _

worstBinary ← ____(n)

n ← 1000 linearMax ← n binaryMax ← __

IF dataSorted = ____ THEN steps ← log2(n)

IF log2(n) _ n THEN OUTPUT "Binary search is faster"

Spot the Error

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

Question 1

A n ← 1000

B OUTPUT 'Linear: ', n

C OUTPUT 'Binary: ', n / 2

Question 2

A range ← 1000

B steps ← range

C WHILE range > 1

D range ← range / 2

E steps ← steps + 1

Question 3

A FOR i ← 1 TO log2(n)

B count ← count + 1

C IF list[i] = target THEN

Question 4

A IF list is sorted THEN

B USE binary search

C ELSE

D USE binary search

E ENDIF

Question 5

A n ← 1000

B binary ← 10

C n ← n + 2

D binary ← binary + 1

Answer Key

Worst-case comparisons: linear versus binary search

Section A: Quick Questions

B — Up to 1000 comparisons

A — About 10 comparisons

B — It halves the remaining range after every comparison

A — log2 n

A — Linear search

Section B: Match the Pairs

comparisons = n → Worst case for a linear search: the target is the last item or missing, so all n items are checked (1000 items means up to 1000 comparisons).

comparisons ≈ log2 n → Worst case for a binary search: each comparison halves the range, so 1000 sorted items need only about 10 comparisons.

Binary search halves the remaining range each time, so it needs far fewer comparisons than linear search on a big sorted list. → middle ← (low + high) DIV 2

Binary search only works on sorted data, so sorting first adds a cost that linear search does not have. → IF list[middle] < target THEN low ← middle + 1

A linear search of 1000 items needs about 10 comparisons in the worst case. → About 10 comparisons is the binary search figure. A linear search may need up to 1000 comparisons (n) in the worst case.

Binary search needs 500 comparisons for 1000 sorted items because it checks half of them. → Binary search does not check half of the items. It halves the range again and again, so it needs only about 10 comparisons (log2 1000).

Section C: Definitions

log2 n — Worst-case comparisons for binary search: it halves a sorted range, so 1000 items need about 10 steps. Linear search needs up to n, so 1000 items could need 1000 comparisons.

Section D: Fill in the Blanks

worstLinear ← n

worstBinary ← log2(n)

n ← 1000
linearMax ← n
binaryMax ← 10

IF dataSorted = TRUE THEN
  steps ← log2(n)

IF log2(n) < n THEN
  OUTPUT "Binary search is faster"

Section E: Spot the Error

C — Binary search halves the range again and again, so its worst case is about log2(n) comparisons (about 10 for 1000 items), not n / 2. The line should output log2(n).

B — The step counter must start at 0 before counting how many times the range can be halved. Starting it at range (1000) would give a wrong answer. It should be steps ← 0.

A — A linear search may have to check every item, so its loop runs up to n times. log2(n) is the worst case for binary search. It should be FOR i ← 1 TO n.

D — Binary search only works on sorted data because it relies on halving the range. If the list is not sorted, you must use linear search. Line 4 should be USE linear search.

C — Doubling the data size means n ← n * 2. Because binary search halves the range, doubling the data adds only one extra step. Adding 2 is not doubling.