Trace a Linear Search

You search for the integer 7 in the array [3, 1, 4, 1, 5, 9, 2, 6, 5, 3]. A linear search walks through each element in order, comparing each to the target.

1. Read array[0] and compare to target

The value at index 0 is 3. Is 3 == 7? No. Advance to index 1.

2. Read array[1] and compare to target

The value at index 1 is 1. Is 1 == 7? No. Advance to index 2.

3. Read array[2] and compare to target

The value at index 2 is 4. Is 4 == 7? No. Advance to index 3.

4. Read array[3] and compare to target

The value at index 3 is 1. Is 1 == 7? No. Advance to index 4.

5. Read array[4] and compare to target

The value at index 4 is 5. Is 5 == 7? No. Advance to index 5.

6. Read array[5] and compare to target

The value at index 5 is 9. Is 9 == 7? No. Advance to index 6.

7. Read array[6] and compare to target

The value at index 6 is 2. Is 2 == 7? No. Advance to index 7.

8. Read array[7] and compare to target

The value at index 7 is 6. Is 6 == 7? No. Advance to index 8.

9. Read array[8] and compare to target

The value at index 8 is 5. Is 5 == 7? No. Advance to index 9.

10. Read array[9] and conclude not found

The value at index 9 is 3. Is 3 == 7? No. All 10 elements checked. The search concludes: 7 was not found.

Why This Matters

The search examined every element — the worst case for linear search. When the target is not present (or is at the last index), linear search must inspect all n elements, giving it O(n) worst-case time complexity.

When the array is sorted, binary search halves the search space each step, achieving O(log n).