Linear search that stops when the target is found

Name:

Date:

Class:

Quick Questions

Shade in the A or B circle for each question.

1. Which WHILE condition makes a linear search of a 10-item array stop as soon as the target is found?

A WHILE Found = FALSE AND Index <= 10 DO

B WHILE Found = FALSE OR Index <= 10 DO

2. What happens to the loop WHILE Found = FALSE AND Index <= 10 when Found is set to TRUE?

A The condition becomes false and the loop stops early

B The loop carries on until Index reaches 10

3. Where should Index ← Index + 1 go in a WHILE linear search?

A Before the loop, so it only runs once

B Inside the loop, so the next item is checked each time

4. Before a WHILE linear search starts, which setup is correct?

A Found ← FALSE and Index ← 1

B Found ← TRUE and Index ← 1

5. A student wants to remember where the target was found. Which line inside the IF is correct?

A Position ← Found

B Position ← Index

Match the Pairs

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

Left column		Right column
1WHILE Found = FALSE AND Index <= 10 DO		AThe REPEAT loop stops when the target is found or the end of the list is passed
2UNTIL Found = TRUE OR Index > 10		BOR keeps the loop running while either condition is true, so after the target is found the loop carries on to the end of the list. It should use AND so the loop stops as soon as Found is TRUE.
3Save the position where the target was found so it can be output after the loop ends		CIF Numbers[Index] = Target THEN Found ← TRUE Position ← Index ENDIF
4Move on to the next item in the list each time round a WHILE loop		DKeep looping only while the target has not been found and the end of the list has not been reached
5WHILE Found = FALSE OR Index <= 10 DO		EIndex ← Index + 1
6WHILE Found = FALSE AND Index <= 10 DO IF Numbers[Index] = Target THEN Found ← TRUE ENDIF ENDWHILE		FIndex ← Index + 1 is missing inside the loop, so Index never changes and the loop repeats the same item forever when the target is not at position 1.

Definitions

WHILE Found = FALSE AND Index <= 10 DO

Fill in the Blanks

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

WHILE Found = FALSE ___ Index <= 10 DO

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

IF List[Index] = Target THEN Found ← ____ Position ← Index

UNTIL Found = TRUE __ Index > 10

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

Spot the Error

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

Question 1

A WHILE NOT Found AND I <= 10 DO

B IF List[I] <> Target THEN

C Found ← TRUE

D ENDIF

E I ← I + 1

F ENDWHILE

Question 2

A WHILE NOT Found AND I <= 10 DO

B IF Names[I] ← Target

C THEN Found ← TRUE

D ELSE I ← I + 1

E ENDIF

F ENDWHILE

Question 3

A WHILE NOT Found AND I <= 10 DO

B IF Marks[I] = Target

C THEN Found ← TRUE

D ELSE I ← I - 1

E ENDIF

F ENDWHILE

Question 4

A WHILE NOT Found OR I <= 10 DO

B IF List[I] = Target THEN

C Found ← TRUE

D ENDIF

E I ← I + 1

F ENDWHILE

Question 5

A REPEAT

B IF List[I] = Target THEN

C Found ← TRUE

D ENDWHILE

E I ← I + 1

F UNTIL Found = TRUE OR I > 10

Answer Key

Linear search that stops when the target is found

Section A: Quick Questions

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

A — The condition becomes false and the loop stops early

B — Inside the loop, so the next item is checked each time

A — Found ← FALSE and Index ← 1

B — Position ← Index

Section B: Match the Pairs

WHILE Found = FALSE AND Index <= 10 DO → Keep looping only while the target has not been found and the end of the list has not been reached

UNTIL Found = TRUE OR Index > 10 → The REPEAT loop stops when the target is found or the end of the list is passed

Save the position where the target was found so it can be output after the loop ends → IF Numbers[Index] = Target THEN Found ← TRUE Position ← Index ENDIF

Move on to the next item in the list each time round a WHILE loop → Index ← Index + 1

WHILE Found = FALSE OR Index <= 10 DO → OR keeps the loop running while either condition is true, so after the target is found the loop carries on to the end of the list. It should use AND so the loop stops as soon as Found is TRUE.

WHILE Found = FALSE AND Index <= 10 DO IF Numbers[Index] = Target THEN Found ← TRUE ENDIF ENDWHILE → Index ← Index + 1 is missing inside the loop, so Index never changes and the loop repeats the same item forever when the target is not at position 1.

Section C: Definitions

WHILE Found = FALSE AND Index <= 10 DO — Keeps searching while the target has not been found AND the end of the list has not been reached, so the loop stops early as soon as Found becomes TRUE.

Section D: Fill in the Blanks

WHILE Found = FALSE AND Index <= 10 DO

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

   IF List[Index] = Target THEN
      Found ← TRUE
      Position ← Index

UNTIL Found = TRUE OR Index > 10

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

Section E: Spot the Error

B — The test must use = so Found only becomes TRUE when the item equals the target. With <> the loop would stop on the first item that does NOT match. It should be IF List[I] = Target THEN.

B — ← assigns a value, it does not compare. A condition in an IF must use = to compare. It should be IF Names[I] = Target.

D — The index must move forward to the next item each time the target is not found. Subtracting 1 would go backwards and loop forever. It should be ELSE I ← I + 1.

A — The loop must stop when the target is found OR the end of the list is reached, so it must keep going only while BOTH conditions are true. OR would keep looping after Found is TRUE. It should be AND.

D — An IF statement is closed with ENDIF. ENDWHILE closes a WHILE loop, and this loop is a REPEAT...UNTIL. Line 4 should be ENDIF.