Unit 5 · Lesson 220 minAcademic review pending

Linear search: inspect until found

Search any array from left to right, define the not-found result, and reason about best and worst cases.

Choose explanation

After this lesson

You should be able to

Implement linear search with an unambiguous not-found result.
State its loop invariant and comparison count.

No ordering required

Linear search compares the target with each element in order and stops at a match. It works on sorted or unsorted data. Decide whether the contract returns the first match, last match, count, or every matching index.

Returning an index requires a distinct not-found value. A signed result can use -1; size_t-based designs commonly return count because it lies one past every valid index.

First matching index

size_t linear_search(const int values[], size_t count, int target) {
    for (size_t i = 0; i < count; i++) {
        if (values[i] == target) {
            return i;
        }
    }
    return count;
}

What has been ruled out?

Before iteration i, the invariant is that target does not occur in indexes 0 through i−1. A successful comparison returns i; reaching count proves no index remains.

The best case uses one comparison. The worst case uses count comparisons, when the target is last or absent. Its running time grows linearly with the number of elements.

Try it yourself

Search [8, 3, 8, 5] for 8 using the given contract. Which index is returned?

Need a hint?

The function returns immediately at the first match.

Check the worked solution

Index 0 is returned.

Quick check

What precondition does linear search require about ordering?

Select an answer to check your thinking.

Why this lesson exists

Syllabus mapping

Linear search

Maps to course outcomes CO1, CO3, CO6.