← WA Computer Science ATAR Unit 1

Worst-case comparisons: linear versus binary search

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.

Part of: WA Computer Science ATAR Year 11 — Standard Algorithms — Module 35

Understanding Worst-case comparisons: linear versus binary search in WA Computer Science ATAR Unit 1

What it does: Finding the middle and discarding half the range after each comparison is what gives binary search about log2 n steps. Linear search checks items one by one, so in the worst case it checks all n items. For n = 1000 that is 1000 comparisons. Worst case means the least lucky situation, such as the target being last or missing. Finding it first is the best case.

Common mistakes: 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). 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.

Class: _____________________ · Name: _____________________ · Date: _________

Free printable worksheet with full answer key — or add this module to a class and your students practise it interactively.

🖨 Print worksheet + answer key Add Worst-case comparisons: linear versus binary search to a class →

This module's key terms are also in a printable crossword (Modules 100–314) and word search (Modules 100–470).

Take this worksheet further — free with Cloodit

Each concept is reinforced from every angle — learned, then applied, then tested.

Learning

Duo

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

About 10 comparisonsUp to 1000 comparisons

Matches

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.

Applying

Meanings

Term

log2 n

Meaning

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.

Practice

n ← 1000

Testing

Gaps

worstLinear ←

Check Answer

Spots

2OUTPUT 'Linear: ', n

3OUTPUT 'Binary: ', n / 2

Cloodit turns curriculum-aligned coding content into journeys students work through one biome at a time.

Students earn collectable badges

Over 100 of them, across seven natural biomes.

Study Buddy

Students build a real study resource

Turns their work into revision material ready for Flash Cards and Exam study.

Diamond Dash — one of Cloodit's live, competitive Sprint games

Students lock in with Sprints

Live, competitive practice for the start of the lesson or a teacher-led lesson finisher.

A Cloodit certificate of achievement, ready to personalise and print

Custom printable certificates

Honour your top performers, or encourage a student who's trying hard — ready to print in seconds.

Add to class →

Quick Questions

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 ✓

Linear search checks items one by one, so in the worst case it checks all n items. For n = 1000 that is 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

Binary search halves the range each time. log2 1000 is just under 10, so about 10 comparisons are enough.

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 ✓

Each comparison throws away half of the remaining items. That is why the number of steps grows like log2 n.

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

A. log2 n ✓

B. n

Binary search needs about log2 n comparisons. n is the worst case for linear search.

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

A. Linear search ✓

B. Binary search

Binary search only works if the data is sorted, because it relies on the order to discard half the range. Linear search works on any list.

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).

Key Term

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.

Fill in the Blanks

1. worstLinear ← n

Hint: Type the variable for the number of items in the array. In the worst case, linear search compares every item.

2. worstBinary ← log2(n)

Hint: Type the function name for the number of times n can be halved. It gives the worst-case steps for binary search.

3. n ← 1000 linearMax ← n binaryMax ← 10

Hint: Type the approximate number of halvings needed to search 1000 sorted items.

4. IF dataSorted = TRUE THEN steps ← log2(n)

Hint: Type the Boolean value that means the data is in order. Binary search only works on sorted data.

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

Hint: Type the comparison operator that shows binary search needs fewer steps than n.

Spot the Error

Question 1

A n ← 1000

B OUTPUT 'Linear: ', n

C OUTPUT 'Binary: ', n / 2

Line 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).

Question 2

A range ← 1000

B steps ← range

C WHILE range > 1

D range ← range / 2

E steps ← steps + 1

Line 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.

Question 3

A FOR i ← 1 TO log2(n)

B count ← count + 1

C IF list[i] = target THEN

Line 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.

Question 4

A IF list is sorted THEN

B USE binary search

C ELSE

D USE binary search

E ENDIF

Line 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.

Question 5

A n ← 1000

B binary ← 10

C n ← n + 2

D binary ← binary + 1

Line 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.

Student with a class code? Join your class →