Standard Methods of a Solution

1What is a searching algorithm?

A searching algorithm is a precise, step-by-step set of instructions a computer follows to find a specific piece of data inside a (possibly huge) dataset — like finding one name in a phone book with a million entries, but doing it in a way a computer can follow exactly, with no "just eyeballing it."

2What is a linear search?

Imagine you're looking for your friend's name in an unsorted stack of index cards. You don't know where it is, and the cards aren't in any order — so your only honest option is to pick up the first card, check it, then the second, then the third, and so on, until you either find the name or run out of cards. That's exactly what a linear search does.

• It starts at the first value in the dataset.
• It checks values one at a time, in order.
• It can be used even if the data is completely unsorted — that's actually its one big advantage over faster searches like binary search, which require sorted data.

Here's the pseudocode from the textbook, worked through step by step. We're searching for target = 11 in data = [5, 2, 8, 1, 9]:

DECLARE data : ARRAY[1:5] OF INTEGER
DECLARE target : INTEGER
DECLARE found : BOOLEAN

data ← [5, 2, 8, 1, 9]
target ← 11
found ← FALSE  // assume not found until proven otherwise

FOR index ← 1 TO 5
   IF data[index] = target THEN
      found ← TRUE
      OUTPUT "Target found"
   ENDIF
NEXT index

IF found = FALSE THEN
   OUTPUT "Target not found"
ENDIF

Notice the shape of this: a flag variable (found) starts as FALSE, and only flips to TRUE if a match is discovered. After the loop finishes, you check the flag to decide what to output. This "flag pattern" shows up constantly in IGCSE pseudocode — get comfortable with it.

1What is a sorting algorithm?

2

pass zero swaps