Sequential search scans a collection from left to right, comparing the target with one item at a time. It returns the index as soon as it finds a match. If it reaches the end without a match, it returns a not-found result such as -1.

The method is useful when a collection is small, unsorted, or stored in a structure that does not support fast random lookup. Its running time depends on how many items the scan must compare.

How Does Sequential Search Scan a Collection?

Linear search begins at index 0 and examines each item in its existing order. For every position, it performs one equality comparison between the current item and the target.

1. Start at the first item.
2. Compare the current item with the target.
3. If they match, stop and return the current index.
4. If they do not match, move to the next item.
5. If no items remain, return the not-found result.

The scan stops early when the target appears near the beginning. It must inspect more of the collection when the target appears later or is absent. A sequential search does not rearrange the collection, so the order remains unchanged.

Linear Search Example: Found and Not Found

Consider this list, where indexes begin at zero:

[14, 3, 27, 8, 19]

To find 8, linear search makes these comparisons:

1. Index 0: compare 14 with 8 — no match.
2. Index 1: compare 3 with 8 — no match.
3. Index 2: compare 27 with 8 — no match.
4. Index 3: compare 8 with 8 — match.

The search returns index 3 after four comparisons.

To find 25, the search compares 25 with 14, 3, 27, 8, and 19. None matches, so the search returns -1 after five comparisons. This is a not-found result because every item was checked.

If the target were 14, the first item would match immediately. That found case would require only one comparison.

Linear Search Pseudocode: Return an Index or Not Found

The following pseudocode returns the first matching index. It returns -1 when the target is missing, including when the collection is empty.

linearSearch(items, target)

1. For index from 0 through the last index in items:
2. Compare items[index] with target.
3. If they are equal, return index.
4. After the loop finishes, return -1.

Returning as soon as a match appears makes the result the first occurrence when duplicate values exist. For example, searching [5, 2, 5] for 5 returns index 0 rather than continuing to index 2.

What Is Linear Search Time Complexity?

Linear search time complexity describes how the number of comparisons grows with the collection size, represented by n.

• Best case: O(1). The target is the first item, so the algorithm performs one comparison.
• Average case: O(n). If a present target is equally likely to occur at any position, the scan makes an average of (n + 1) / 2 comparisons. This simplifies to O(n).
• Worst case: O(n). The target is the final item or is not present, so the algorithm checks all n items.

The exact comparison count follows the trace: position i requires i + 1 comparisons, while an absent target requires n. The algorithm uses O(1) auxiliary space because it stores only the current index and target-related variables; it does not create another collection.