# Linear Search Algorithm on 1D Arrays

- **Track:** Cambridge IGCSE™ Computer Science (0478 / 0984) (CAMBRIDGE IGCSE 0478)
- **Module:** Section 7: Algorithm Design & Problem-Solving
- **Estimated Duration:** 10 minutes
- **Access:** Open Theory (All-Access for Interactive IDE & Autotests)

---

## Theory & Conceptual Background

A **Linear Search** (also called a sequential search) is an algorithm that inspects every element of a one-dimensional array one by one in sequence, starting from the first position (`Index = 1`), until either the target element is located or the entire array has been examined.

---

## 1. How Linear Search Works

```text
Target: 42
Array: [ 17,  8,  42,  95,  31 ]
          ▲   ▲    ▲
          │   │    └─ Match found! Set Found <- TRUE, stop search.
          │   └────── Check Index 2 (8 != 42) -> Next
          └────────── Check Index 1 (17 != 42) -> Next
```

### Operational Steps:

1. **Initialize Flag and Pointer**:

- `Found <- FALSE` (tracks whether the target item has been located).
- `FoundIndex <- -1` (records the index location where the target resides).
- `Index <- 1` (starting array index).

1. **Sequential Loop**:

- Repeat while `Index <= MaxSize` **AND** `Found = FALSE`.
- If `Array[Index] = Target`, set `Found <- TRUE` and `FoundIndex <- Index`.
- Always increment `Index <- Index + 1` to advance to the next position.

1. **Post-Loop Verification**:

- Check `IF Found = TRUE`: output the index position.
- `ELSE`: output a notification that the item was not present in the dataset.

---

## 2. Efficiency & Characteristics

  
| Characteristic | Linear Search |
| --- | --- |
| **Data Order Requirement** | **None**: Operates effectively on completely unsorted data. |
| **Best-Case Efficiency** | $1$ comparison (target is at index 1). |
| **Worst-Case Efficiency** | $N$ comparisons (target is at the very last index or completely absent). |
| **Average Comparisons** | $\approx N / 2$ comparisons. |
| **Suitability** | Ideal for small lists or unsorted data where overhead of sorting would exceed search savings. |

---

## Interactive Exercises & Autotest Specifications

### Exercise 1: Exam-Style Check: Linear Search Prerequisites & Efficiency (Multiple choice, 25 XP)

**Instructions:**
Which statement is TRUE regarding the requirements and operation of a linear search algorithm on a 1D array?

**Options:**
- **A**: The array must be sorted in ascending order before a linear search can execute.
- **B**: Linear search compares the target item against the middle element on every pass.
- **C**: Linear search is always faster than binary search regardless of array size.
- **D**: Linear search can operate directly on unsorted arrays by checking elements sequentially from start to finish.


**Autotest Expectations:**
- **Linear search characteristics identified**: `selection_match` -> Expected: `opt_unsorted`

### Exercise 2: Exam-Style Question: Complete the Linear Search Control Logic (Fill in blank, 35 XP)

**Instructions:**
Complete the missing keywords and variable values in the Cambridge linear search template for an array of 50 integers:


**Starter Code:**
```text
{"prompt":"Complete the missing keywords and variable values in the Cambridge linear search template for an array of 50 integers:","template":"```pseudocode\nFound <- [blank_1]\nIndex <- 1\nWHILE (Index <= 50) AND (Found = FALSE) DO\n    IF Scores[Index] = Target THEN\n        Found <- [blank_2]\n        Location <- Index\n    ENDIF\n    Index <- Index + [blank_3]\nENDWHILE\n```","word_bank":["FALSE","TRUE","1","0","50","Index"]}
```

**Autotest Expectations:**
- **Initial flag is FALSE**: `text_exact` -> Expected: `FALSE`
- **Found flag updated to TRUE**: `text_exact` -> Expected: `TRUE`
- **Index incremented by 1**: `text_exact` -> Expected: `1`

### Exercise 3: Independent Practice: First matching position (Pseudocode, 30 XP)

**Instructions:**
Read five integers into an array, then a target integer. Output the position of the first matching item (positions 1 to 5), or 0 if absent.

Write a complete program. Read inputs in the stated order. Output only the requested results, one per line, without input prompts. Test with your own values before submitting.


**Starter Code:**
```text
// Plan your solution, then write your program.

```

**Autotest Expectations:**
- **First item**: `test_case` -> Expected: `{&quot;inputs&quot;:[9,4,7,4,2,9],&quot;output&quot;:&quot;1&quot;}`
- **Last item**: `test_case` -> Expected: `{&quot;inputs&quot;:[9,4,7,4,2,2],&quot;output&quot;:&quot;5&quot;}`
- **Absent**: `test_case` -> Expected: `{&quot;inputs&quot;:[9,4,7,4,2,8],&quot;output&quot;:&quot;0&quot;}`
- **Repeated target**: `test_case` -> Expected: `{&quot;inputs&quot;:[9,4,7,4,2,4],&quot;output&quot;:&quot;2&quot;}`