Linear Search

Linear search (also called sequential search) is the simplest searching algorithm. It works by checking each item in a list, one by one, from the beginning to the end, until the desired item is found or the entire list has been searched.

---

How Linear Search Works

The algorithm follows these steps:

1. Start at the first element of the list.
2. Compare the current element with the target value (the item you are looking for).
3. If the current element matches the target, return its position — the search is complete.
4. If it does not match, move to the next element.
5. Repeat steps 2–4 until either the target is found or you have checked every element.
6. If the end of the list is reached without finding the target, report that the item is not found.

The control flow of the linear search loop:

graph TD
    A["Start: i = 0"] --> B{"i less than length(list)?"}
    B -->|No| C["Return -1 (not found)"]
    B -->|Yes| D{"list[i] = target?"}
    D -->|Yes| E["Return i (found)"]
    D -->|No| F["i = i + 1"]
    F --> B

---

Pseudocode for Linear Search

FUNCTION linearSearch(list, target)
    FOR i = 0 TO LENGTH(list) - 1
        IF list[i] = target THEN
            RETURN i
        ENDIF
    NEXT i
    RETURN -1
ENDFUNCTION

The function returns the index (position) of the target if found, or -1 if the target is not in the list.

---

Worked Example

Consider the list: [7, 3, 12, 9, 1, 5]

Target: 9

Step	Index	Element	Match?
1	0	7	No
2	1	3	No
3	2	12	No
4	3	9	Yes

The target 9 is found at index 3. The search stops here.

Target: 8

Step	Index	Element	Match?
1	0	7	No
2	1	3	No
3	2	12	No
4	3	9	No
5	4	1	No
6	5	5	No

All elements checked — 8 is not in the list. Return -1.

---

Advantages of Linear Search

• Simple to understand and implement — it requires very little code.
• Works on unsorted data — the list does not need to be in any particular order.
• Works on any data structure — arrays, linked lists, etc.
• No pre-processing required — you can search immediately without sorting first.

Disadvantages of Linear Search

• Slow for large datasets — in the worst case, every element must be checked.
• Inefficient compared to binary search on sorted data.

---

Efficiency of Linear Search

The performance of a search algorithm is measured by how many comparisons it makes:

Case	Comparisons	Explanation
Best case	1	The target is the first element
Worst case	n	The target is the last element or not in the list
Average case	n/2	On average, half the list is checked

Where n is the number of items in the list.

As the list gets larger, the number of comparisons grows linearly — hence the name "linear search." If the list doubles in size, the worst-case number of comparisons also doubles.

Exam Tip: If asked about the efficiency of linear search, state that it has a time complexity of O(n), meaning the time taken grows proportionally to the size of the list. You should also mention that it is less efficient than binary search for sorted data but has the advantage of working on unsorted lists.

---

When to Use Linear Search

Linear search is appropriate when:

• The dataset is small
• The data is unsorted and you cannot sort it first
• You only need to search once (sorting first would be more expensive)
• You are searching a linked list (where binary search is impractical)

---

Key Points

• Linear search checks each item in order from start to finish.
• It works on both sorted and unsorted data.
• Best case: 1 comparison. Worst case: n comparisons.
• Time complexity is O(n).
• Simple but inefficient for large datasets.

---

Extended Worked Examples

Worked Example A: Searching Strings

Linear search is not restricted to numbers. Consider searching a list of names for "Priya".

names = ["Amira", "Ben", "Chen", "Daria", "Priya", "Sam"]
target = "Priya"
found = FALSE
position = -1
FOR i = 0 TO LENGTH(names) - 1
    IF names[i] = target THEN
        found = TRUE
        position = i
        EXIT FOR
    ENDIF
NEXT i
IF found = TRUE THEN
    OUTPUT "Found at index " + position
ELSE
    OUTPUT "Not found"
ENDIF

Trace table:

i	names[i]	Match?	found	position
—	—	—	FALSE	-1
0	Amira	No	FALSE	-1
1	Ben	No	FALSE	-1
2	Chen	No	FALSE	-1
3	Daria	No	FALSE	-1
4	Priya	Yes	TRUE	4

The EXIT FOR statement terminates the loop as soon as the target is found, avoiding unnecessary comparisons on the remainder of the list. Without it, linear search would continue through every remaining element.

Worked Example B: Counting Occurrences (Variant)

Sometimes you do not want the first match — you want to know how many times a value appears. A slight variant of linear search counts occurrences:

FUNCTION countOccurrences(list, target)
    count = 0
    FOR i = 0 TO LENGTH(list) - 1
        IF list[i] = target THEN
            count = count + 1
        ENDIF
    NEXT i
    RETURN count
ENDFUNCTION

For [3, 7, 3, 9, 3, 1, 3] and target 3, the trace: