Standard Algorithm & Logic Patterns: Linear Search Algorithm Guide (Copy)

Linear Search Algorithm Guide

What Linear Search Is (AS Level Definition)

• Linear search is a simple searching algorithm that:
  • Checks elements one by one
  • From the start to the end
• Used to determine whether:
  • A value exists in a list
  • And optionally where it is located
• It does not require sorted data

---

Core Examiner Rule (Must Remember)

• Linear search:
  • Works on any list
  • Is easy to write
  • Is inefficient for large data
• Examiners expect:
  • Correct logic
  • Correct loop control
  • Correct stopping conditions

---

When Linear Search Is The Correct Choice

• Data is:
  • Unsorted
  • Small
  • Entered one-by-one
• When:
  • Early termination is allowed
  • Simplicity matters more than speed

---

Standard Linear Search Logic (Conceptual Steps)

1. Start at the first element
2. Compare current element with target
3. If equal → mark as found
4. If not → move to next element
5. Stop when:
   • Found
   • OR end of list reached

---

Linear Search Pattern (Key Variables)

Purpose	Variable
Target value	target
Loop index	i
Found flag	found
Data list	arr

---

Linear Search Without Early Termination (Basic Pattern)

Pseudocode

found ← FALSE

FOR i ← 1 TO n
  IF arr[i] = target THEN
    found ← TRUE
  ENDIF
NEXT i

IF found = TRUE THEN
  OUTPUT "Found"
ELSE
  OUTPUT "Not Found"
ENDIF

---

Examiner Notes

• Always checks all elements
• Works even if value appears multiple times
• Slightly inefficient but logically valid

---

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 AS Level Computer Science Full Scale Course

Linear Search With Early Termination (Preferred In Exams)

Why Early Termination Matters

• Stops searching once the value is found
• Reduces unnecessary comparisons
• Shows efficiency awareness

---

Pseudocode (Exam-Preferred)

found ← FALSE
i ← 1

WHILE i <= n AND found = FALSE DO
  IF arr[i] = target THEN
    found ← TRUE
  ELSE
    i ← i + 1
  ENDIF
ENDWHILE

IF found = TRUE THEN
  OUTPUT "Found"
ELSE
  OUTPUT "Not Found"
ENDIF

---

Key Points

• Two loop conditions:
  • Not reached end
  • Not found yet
• Loop stops as soon as match occurs

---

Linear Search With Position Output

Problem

• Find the position of the target value

---

Pseudocode

found ← FALSE
i ← 1

WHILE i <= n AND found = FALSE DO
  IF arr[i] = target THEN
    found ← TRUE
  ELSE
    i ← i + 1
  ENDIF
ENDWHILE

IF found = TRUE THEN
  OUTPUT i
ELSE
  OUTPUT "Not Found"
ENDIF

---

Examiner Tip

• Output index only after loop ends
• i holds the correct position

---

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 AS Level Computer Science Full Scale Course

Linear Search On User Input (No Array)

When This Is Used

• Values are processed once
• No need to store data

---

Example: Search While Inputting

found ← FALSE
count ← 1

WHILE count <= 10 AND found = FALSE DO
  INPUT num
  IF num = target THEN
    found ← TRUE
  ELSE
    count ← count + 1
  ENDIF
ENDWHILE

IF found = TRUE THEN
  OUTPUT "Found"
ELSE
  OUTPUT "Not Found"
ENDIF

---

Linear Search With Strings

Searching For A Character In A String

found ← FALSE
i ← 1

WHILE i <= LENGTH(text) AND found = FALSE DO
  IF text[i] = targetChar THEN
    found ← TRUE
  ELSE
    i ← i + 1
  ENDIF
ENDWHILE

IF found = TRUE THEN
  OUTPUT "Found"
ELSE
  OUTPUT "Not Found"
ENDIF

---

Linear Search With Count (Multiple Occurrences)

Problem

• Count how many times target appears

---

Pseudocode

count ← 0

FOR i ← 1 TO n
  IF arr[i] = target THEN
    count ← count + 1
  ENDIF
NEXT i

OUTPUT count

---

Examiner Note

• Early termination not used
• Must scan entire list

---

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 AS Level Computer Science Full Scale Course

Linear Search Trace Table Example

Pseudocode

arr = [4, 7, 2, 9]
target = 2

i	arr[i]	found
1	4	FALSE
2	7	FALSE
3	2	TRUE

• Loop stops at i = 3

---

Common Linear Search Mistakes (High-Frequency)

Mistake 1: Forgetting To Update Index

WHILE found = FALSE DO

• Infinite loop risk

---

Mistake 2: Checking Wrong Variable

IF i = target THEN

• Must compare arr[i], not i

---

Mistake 3: Outputting Inside Loop

• Leads to multiple outputs

---

Mistake 4: Accessing Out Of Range

i <= n + 1

---

Linear Search Vs Other Searches (AS Level View)

Feature	Linear Search
Requires sorted data	No
Easy to implement	Yes
Efficient for large lists	No
Early termination possible	Yes

---

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 AS Level Computer Science Full Scale Course

Examiner-Approved Explanation Language

• “The algorithm checks each element sequentially”
• “The search stops when the value is found”
• “If the value is not found, the loop ends at the last element”

---

Exam-Ready Linear Search Template

found ← FALSE
index ← 1

WHILE index <= n AND found = FALSE DO
  IF arr[index] = target THEN
    found ← TRUE
  ELSE
    index ← index + 1
  ENDIF
ENDWHILE

IF found = TRUE THEN
  OUTPUT index / "Found"
ELSE
  OUTPUT "Not Found"
ENDIF

---

One-Line Rules To Memorise

• Linear search checks one by one
• No sorting required
• Early termination improves efficiency
• Flags control search flow
• Simple logic scores full marks