Linear search: how it works

Name:

Date:

Class:

Quick Questions

Shade in the A or B circle for each question.

1. A linear search checks the items of a list in which order?

A One at a time, from the start of the list

B Starting from the middle of the list

2. Can a linear search be used on a list that is NOT sorted?

A No, the list must be sorted first

B Yes, it works on unsorted data

3. A linear search is looking for the target 7 in the list [4, 9, 7, 2]. How many items are checked before 7 is found?

A 3

B 4

4. A linear search looks for the target 5 in [8, 3, 6, 1]. What is the result?

A Not found, after checking all 4 items

B Not found, after checking only the first item

5. What is the BEST case for a linear search?

A The target is the last item, so only 1 check is needed

B The target is the first item, so only 1 check is needed

Match the Pairs

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

Left column		Right column
1FOR Index ← 1 TO 10 IF Names[Index] = Target THEN Found ← TRUE		AThe average case is about half the list, around 50 checks. Only the best case needs 1 check.
2Found ← FALSE		BFOR Index ← 1 TO 10
3Best case: the target is the very first item, so only 1 check is needed		CChecks each item in the list in turn, starting from the first, to see if it equals the target
4Worst case: the target is the last item or not in the list, so every item is checked		DA linear search works on unsorted data. It simply checks each item in turn, so no sorting is needed.
5Linear search needs the list to be sorted into order first, otherwise it cannot work		EStarts the search with the target not yet found; it only becomes TRUE if a matching item turns up
6On average, a linear search of 100 items needs 1 check to find the target		FNames[1] = Target

Definitions

linear search

Fill in the Blanks

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

Target ← 7 Index ← 0 Found ← _____

// Scores has 5 items (index 0 to 4) FOR Index ← 0 TO _

FOR Index ← 0 TO 4 IF Scores[Index] _ Target THEN Found ← TRUE

IF Scores[Index] = Target THEN Found ← ____ ENDIF

// Worst case: target is last or missing // List has 5 items, so most checks is: Checks ← _

Spot the Error

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

Question 1

A Found ← TRUE

B FOR I ← 1 TO 10

C IF List[I] = Target THEN

D Found ← TRUE

E ENDIF

F NEXT I

Question 2

A Found ← FALSE

B FOR I ← 1 TO 9

C IF List[I] = Target THEN

D Found ← TRUE

E ENDIF

F NEXT I

Question 3

A Found ← FALSE

B FOR I ← 1 TO 10

C IF List[I] ← Target THEN

D Found ← TRUE

E ENDIF

F NEXT I

Question 4

A Found ← FALSE

B FOR I ← 1 TO 10

C IF List[I] = Target THEN

D Found ← FALSE

E ENDIF

F NEXT I

Question 5

A Position ← 0

B FOR I ← 1 TO 10

C IF List[I] = Target THEN

D Position ← Target

E ENDIF

F NEXT I

Answer Key

Linear search: how it works

Section A: Quick Questions

A — One at a time, from the start of the list

B — Yes, it works on unsorted data

A — 3

A — Not found, after checking all 4 items

B — The target is the first item, so only 1 check is needed

Section B: Match the Pairs

FOR Index ← 1 TO 10 IF Names[Index] = Target THEN Found ← TRUE → Checks each item in the list in turn, starting from the first, to see if it equals the target

Found ← FALSE → Starts the search with the target not yet found; it only becomes TRUE if a matching item turns up

Best case: the target is the very first item, so only 1 check is needed → Names[1] = Target

Worst case: the target is the last item or not in the list, so every item is checked → FOR Index ← 1 TO 10

Linear search needs the list to be sorted into order first, otherwise it cannot work → A linear search works on unsorted data. It simply checks each item in turn, so no sorting is needed.

On average, a linear search of 100 items needs 1 check to find the target → The average case is about half the list, around 50 checks. Only the best case needs 1 check.

Section C: Definitions

linear search — Checks each item in a list in turn, from the start, until the target is found or the end of the list is reached. It works on unsorted data.

Section D: Fill in the Blanks

Target ← 7
Index ← 0
Found ← FALSE

// Scores has 5 items (index 0 to 4)
FOR Index ← 0 TO 4

FOR Index ← 0 TO 4
   IF Scores[Index] = Target THEN
      Found ← TRUE

IF Scores[Index] = Target THEN
   Found ← TRUE
ENDIF

// Worst case: target is last or missing
// List has 5 items, so most checks is:
Checks ← 5

Section E: Spot the Error

A — The flag must start as FALSE because the target has not been found yet. If it starts as TRUE, the search would report found even when the target is not in the list. It should be Found ← FALSE.

B — The list has 10 items, so the loop must check every one, from 1 to 10. Stopping at 9 means the last item is never checked. It should be FOR I ← 1 TO 10.

C — A search compares each item with the target, so it needs the comparison operator =. The arrow ← is for assignment. It should be IF List[I] = Target THEN.

D — When the current item matches the target, the flag must be set to TRUE to record that the target was found. Setting it to FALSE means the match is never recorded. It should be Found ← TRUE.

D — The position of a match is the index of the item, which is the loop counter I. Storing Target just copies the value being searched for. It should be Position ← I.