C++UCS301
SearchingC++17

Linear Search

Linear search checks elements one at a time and works on unsorted data with no preprocessing.

Open this in the visual lab

What to understand

  • Sequential scan
  • Sentinel variant
  • First and last occurrence
  • When O(n) is acceptable

Remember this

  1. 1Works on any sequence
  2. 2Can stop after a match
  3. 3Best case O(1), worst O(n)

Detailed notes

Linear search examines candidates in sequence until it finds the target or exhausts the range. It needs no sorting, indexing, or random-access capability, so it works on arrays, linked lists, streams, and tiny collections.

Its best case is immediate success, while average and worst work grow with n. For one query this simplicity is often optimal; repeated queries may justify sorting or building an index.

How it works

  1. 1Start at the first candidate.
  2. 2Compare each value with the target.
  3. 3Return immediately on the required match.
  4. 4Return a clear failure sentinel after the range ends.

Worked trace

Find 18 sequentially

[4, 9, 13, 18, 25]
  1. 1Compare 4 with 18: different.
  2. 2Compare 9 with 18: different.
  3. 3Compare 13 with 18: different.
  4. 4Compare 18 with 18: match; stop.
Result: Found at index 3 after four comparisons

Where it is used

  • Unsorted or streaming input
  • Small collections where preprocessing costs more
  • Searching linked structures

Common mistakes

  • Returning the value when the API promises an index
  • Continuing after finding the first required match
  • Using -1 with an unsigned return type

Complexity analysis

OperationBestAverageWorstExtra space
SearchO(1)O(n)O(n)O(1)

C++ implementation

C++17 reference
main.cpp

Linear search

Return the index of the first match or -1 when the target is absent.

int linearSearch(const vector<int>& values, int target) {
    for (int i = 0; i < static_cast<int>(values.size()); ++i) {
        if (values[i] == target) return i;
    }
    return -1;
}
6 linesUTF-8 · C++ study reference

Exam & viva

Open a prompt when you are ready to check your answer.