Arrays, Records & Data Handling: Searching Algorithms In Arrays (Linear Search Logic) (Copy)

Searching Algorithms In Arrays (Linear Search Logic) (Cambridge Standard – O Level 2210 + IGCSE 0478)

Purpose Of Linear Search In Cambridge Pseudocode

• Linear search is used to:
  • Find a specific value in an array
  • Check whether an item exists
• Cambridge tests linear search to assess:
  • Correct traversal logic
  • Safe loop termination
  • Use of flags and boundary conditions
• Linear search appears frequently in:
  • Pre-release material
  • Section B algorithm modification questions
  • Trace table questions

What Cambridge Means By Linear Search

• Linear search:
  • Starts at the first element
  • Checks elements one by one
  • Stops when:
    • The target is found, OR
    • The end of the array is reached
• Works on:
  • Unsorted arrays
  • Sorted arrays (but not optimised)

Core Characteristics Of Linear Search

• Sequential access
• One comparison per element
• Worst-case complexity:
  • All elements checked
• Simplicity over efficiency
• Preferred by Cambridge for clarity

Core Linear Search Structure (Cambridge Standard)

Flag-Controlled Linear Search (Most Common)

• found ← FALSE
• index ← lowerBound
• WHILE found = FALSE AND index <= upperBound DO
  • IF arrayName[index] = target THEN
    • found ← TRUE
  • ELSE
    • index ← index + 1
  • ENDIF
• ENDWHILE

Why This Structure Is Examiner-Preferred

• Clear stopping conditions
• Safe termination
• Easy to trace
• Prevents out-of-range access

Meaning Of Each Component

• found:
  • Boolean flag
  • Tracks whether target has been found
• index:
  • Tracks current position
• boundary condition:
  • Prevents invalid index access

Written and Compiled By Sir Hunain Zia (AYLOTI), World Record Holder With 154 Total A Grades, 7 Distinctions and 11 World Records For Educate A Change O Level And IGCSE Computer Science Full Scale Course

Linear Search Using FOR Loop (Also Acceptable)

FOR-Based Search Pattern

• found ← FALSE
• FOR i ← lowerBound TO upperBound
  • IF arrayName[i] = target THEN
    • found ← TRUE
  • ENDIF
• ENDFOR

Examiner Commentary On FOR-Based Search

• This version:
  • Continues searching even after found
• Acceptable when:
  • Question does not require early termination
• Less efficient but:
  • Still logically correct

Early Exit Using FOR Loop (Advanced, Use Carefully)

• found ← FALSE
• FOR i ← lowerBound TO upperBound
  • IF arrayName[i] = target THEN
    • found ← TRUE
    • EXIT LOOP
  • ENDIF
• ENDFOR

Examiner Note

• EXIT LOOP:
  • Must be used correctly
  • Must not be overused
• WHILE loop is safer if early exit is required

Linear Search Without Flag (Index-Controlled)

Alternative Pattern

• index ← lowerBound
• WHILE index <= upperBound AND arrayName[index] <> target DO
  • index ← index + 1
• ENDWHILE

Post-Search Check

• IF index <= upperBound THEN
  • OUTPUT “Found”
• ELSE
  • OUTPUT “Not found”
• ENDIF

Examiner Focus

• Boundary condition must be present
• index must be checked after loop
• Avoid ambiguous termination logic

Written and Compiled By Sir Hunain Zia (AYLOTI), World Record Holder With 154 Total A Grades, 7 Distinctions and 11 World Records For Educate A Change O Level And IGCSE Computer Science Full Scale Course

Linear Search And Input Validation

• Linear search is often used to:
  • Check if an ID already exists
  • Prevent duplicate entries

Example

• found ← FALSE
• FOR i ← 1 TO totalRecords
  • IF idArray[i] = newID THEN
    • found ← TRUE
  • ENDIF
• ENDFOR
• IF found = TRUE THEN
  • OUTPUT “Duplicate ID”
• ELSE
  • OUTPUT “ID accepted”
• ENDIF

Linear Search And Selection Logic

• Searching does not replace selection
• Selection is used:
  • After search result is known

Example:

• IF found = TRUE THEN
  • OUTPUT “Record found”
• ELSE
  • OUTPUT “Record not found”
• ENDIF

Linear Search And Arrays With Bounds

• Loop bounds must:
  • Match declared array range
• Common declarations:
  • [1:n]
  • [0:n-1]

Examiner Trap

• Using:
  • FOR i ← 1 TO n
• When array declared:
  • [0:n-1]

Written and Compiled By Sir Hunain Zia (AYLOTI), World Record Holder With 154 Total A Grades, 7 Distinctions and 11 World Records For Educate A Change O Level And IGCSE Computer Science Full Scale Course

Linear Search And Two-Dimensional Arrays (Contextual Use)

• Linear search can be extended to 2D arrays
• Requires nested loops

Example

• found ← FALSE
• FOR r ← rowLower TO rowUpper
  • FOR c ← colLower TO colUpper
    • IF data[r,c] = target THEN
      • found ← TRUE
    • ENDIF
  • ENDFOR
• ENDFOR

Linear Search And Trace Tables

Typical Trace Variables

• index
• arrayName[index]
• found

Trace Behaviour

• Each iteration:
  • One comparison
• Loop stops:
  • When found = TRUE
  • Or boundary reached

Common Trace Errors

• Skipping comparison
• Forgetting boundary condition
• Assuming search stops automatically

Linear Search In Pre-Release Material

• Pre-release tasks frequently:
  • Require searching arrays
  • Require modification of search conditions
• Cambridge often asks:
  • “Modify the algorithm to check whether…”

Linear Search In Section B Modifications

• Common modifications include:
  • Searching only part of array
  • Searching with additional condition
  • Returning position instead of flag

Returning Position Example

• position ← -1
• FOR i ← 1 TO n
  • IF arrayName[i] = target THEN
    • position ← i
  • ENDIF
• ENDFOR
• IF position <> -1 THEN
  • OUTPUT position
• ELSE
  • OUTPUT “Not found”
• ENDIF

Examiner Expectation

• Clear “not found” indicator
• Correct index value returned

Written and Compiled By Sir Hunain Zia (AYLOTI), World Record Holder With 154 Total A Grades, 7 Distinctions and 11 World Records For Educate A Change O Level And IGCSE Computer Science Full Scale Course

Common Linear Search Errors (Guaranteed Mark Loss)

• Missing boundary condition
• Infinite loop
• Using wrong comparison operator
• Modifying loop index manually
• Accessing out-of-range index
• Forgetting to initialise found flag

Best-Practice Linear Search Strategy For Paper 2

• Prefer WHILE loop when early exit is required
• Always include boundary condition
• Use Boolean flag for clarity
• Keep search logic simple
• Separate search logic from output logic

Final Quality Checklist

• Index initialised correctly
• Boundary condition included
• Comparison correct
• Termination guaranteed
• Result handled after loop
• Logic traceable step-by-step

Final Lock-In Rules

• Linear search checks one element at a time
• Boundary control prevents errors
• Flag variables improve clarity
• WHILE loop is safest for early termination
• Clean linear search logic = reliable Paper 2 marks

Written and Compiled By Sir Hunain Zia (AYLOTI), World Record Holder With 154 Total A Grades, 7 Distinctions and 11 World Records For Educate A Change O Level And IGCSE Computer Science Full Scale Course