Linear search in pseudocode

Name:

Date:

Class:

Quick Questions

Shade in the A or B circle for each question.

1. Where does a linear search start looking in an array?

A At the first element

B At the middle element

2. Which line correctly compares an array element with the target in pseudocode?

A IF Names[Index] ← Target THEN

B IF Names[Index] = Target THEN

3. What is the best way to set up the found flag before the search starts?

A Found ← FALSE

B Found ← TRUE

4. Which data type should the Found flag be declared as?

A DECLARE Found : BOOLEAN

B DECLARE Found : INTEGER

5. Which WHILE condition lets a linear search stop early once the target is found?

A WHILE Found = TRUE AND Index <= 10 DO

B WHILE Found = FALSE AND Index <= 10 DO

Match the Pairs

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

Left column		Right column
1WHILE Index <= 10 AND Found = FALSE DO		ACompares the current array element with the value being searched for
2IF Item[Index] = Target THEN		BFound ← TRUE
3A BOOLEAN found flag starts as FALSE and is set to TRUE when the target is matched		CIndex is never increased inside the loop, so the same element is checked forever. Add Index ← Index + 1 inside the loop.
4If the loop ends and the flag is still FALSE, tell the user the target was not found		DIF Found = FALSE THEN OUTPUT "Not found" ENDIF
5IF Item[Index] ← Target THEN		EKeeps searching only while elements remain and no match has been found, so the search stops early
6Index ← 1 WHILE Index <= 10 AND Found = FALSE DO IF Item[Index] = Target THEN Found ← TRUE ENDIF ENDWHILE		FUses the assignment arrow ← instead of = to compare. It should be IF Item[Index] = Target THEN.

Definitions

linear search

Fill in the Blanks

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

Found ← _____ Index ← 1 WHILE Index <= 10 AND Found = FALSE DO

Index ← 1 WHILE Index <= 10 ___ Found = FALSE DO IF Item[Index] = Target THEN

WHILE Index <= 10 AND Found = FALSE DO IF Item[Index] _ Target THEN Found ← TRUE

Index ← Index + 1 ________ IF Found = FALSE THEN

IF Found = FALSE THEN ______ "Not found" ENDIF

Spot the Error

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

Question 1

A Found ← FALSE

B FOR Pos ← 5 TO 1

C IF Names[Pos] = Target THEN

D Found ← TRUE

E ENDIF

F NEXT Pos

Question 2

A WHILE Found AND Pos < 6 DO

B IF Names[Pos] = Target THEN

C Found ← TRUE

D ENDIF

E Pos ← Pos + 1

F ENDWHILE

Question 3

A Found ← "FALSE"

B FOR Pos ← 1 TO 5

C IF Scores[Pos] = Target THEN

D Found ← TRUE

E ENDIF

F NEXT Pos

Question 4

A FOR Index ← 1 TO 5

B IF Item = Target THEN

C OUTPUT "Found at ", Index

D ENDIF

E NEXT Index

Question 5

A Found ← FALSE

B FOR Pos ← 1 TO 8

C IF Words[Pos] <> Target THEN

D Found ← TRUE

E ENDIF

F NEXT Pos

Answer Key

Linear search in pseudocode

Section A: Quick Questions

A — At the first element

B — IF Names[Index] = Target THEN

A — Found ← FALSE

A — DECLARE Found : BOOLEAN

B — WHILE Found = FALSE AND Index <= 10 DO

Section B: Match the Pairs

WHILE Index <= 10 AND Found = FALSE DO → Keeps searching only while elements remain and no match has been found, so the search stops early

IF Item[Index] = Target THEN → Compares the current array element with the value being searched for

A BOOLEAN found flag starts as FALSE and is set to TRUE when the target is matched → Found ← TRUE

If the loop ends and the flag is still FALSE, tell the user the target was not found → IF Found = FALSE THEN OUTPUT "Not found" ENDIF

IF Item[Index] ← Target THEN → Uses the assignment arrow ← instead of = to compare. It should be IF Item[Index] = Target THEN.

Index ← 1 WHILE Index <= 10 AND Found = FALSE DO IF Item[Index] = Target THEN Found ← TRUE ENDIF ENDWHILE → Index is never increased inside the loop, so the same element is checked forever. Add Index ← Index + 1 inside the loop.

Section C: Definitions

linear search — Checks each array element in order from the first, comparing it with the target, until a match is found or the end of the array is reached.

Section D: Fill in the Blanks

Found ← FALSE
Index ← 1
WHILE Index <= 10 AND Found = FALSE DO

Index ← 1
WHILE Index <= 10 AND Found = FALSE DO
    IF Item[Index] = Target THEN

WHILE Index <= 10 AND Found = FALSE DO
    IF Item[Index] = Target THEN
        Found ← TRUE

    Index ← Index + 1
ENDWHILE
IF Found = FALSE THEN

IF Found = FALSE THEN
    OUTPUT "Not found"
ENDIF

Section E: Spot the Error

B — A linear search starts at the first element and works forwards. FOR Pos ← 5 TO 1 counts down without a STEP, so the loop would not run properly. It should be FOR Pos ← 1 TO 5.

A — Found starts as FALSE, so the condition Found AND ... is false straight away and the loop never runs. To keep searching until a match is found, the condition must use NOT Found.

A — Found is a BOOLEAN flag. Putting quotes around FALSE makes it a string. It should be Found ← FALSE with no quotes.

B — The condition compares the whole array with the target. Each element must be compared in turn, so it should be IF Item[Index] = Target THEN.

C — A linear search looks for an element equal to the target. Using <> would flag every element that does not match. It should be IF Words[Pos] = Target THEN.