Linear Search

Introduction

Linear search, also known as sequential search, is the most fundamental searching algorithm in computer science. It works by examining each element of a collection one by one, in sequence, until the desired element is found or the entire collection has been traversed. Unlike more advanced searching algorithms, linear search does not require the data to be sorted or organized in any particular way.

The algorithm's simplicity is both its greatest strength and its greatest limitation. While it is trivially easy to implement and understand, its performance degrades linearly with the size of the input. For a collection of n elements, linear search may need to examine all n elements in the worst case, giving it a time complexity of O(n). Despite this, linear search remains indispensable in situations where data is unsorted, the collection is small, or when searching through data structures that do not support random access.

"Linear search is the brute-force approach to searching. It is the algorithm you use when you have no information about the structure of the data." -- Robert Sedgewick, Algorithms (4th Edition)

The algorithm dates back to the earliest days of computing and is often the first search algorithm taught in introductory computer science courses. Its directness makes it an excellent starting point for understanding more sophisticated search techniques such as binary search, hash-based search, and tree-based search.

How It Works

Basic Approach

Linear search follows a straightforward procedure:

1. Start at the first element of the array (index 0).
2. Compare the current element with the target value.
3. If the current element matches the target, return its index.
4. If the current element does not match, move to the next element.
5. Repeat steps 2-4 until the target is found or the end of the array is reached.
6. If the end of the array is reached without finding the target, return -1 (or indicate "not found").

Visual Illustration

Consider searching for the value 7 in the array [3, 8, 1, 7, 5, 2]:

• Step 1: Check index 0 (value 3). Not a match. Move forward.
• Step 2: Check index 1 (value 8). Not a match. Move forward.
• Step 3: Check index 2 (value 1). Not a match. Move forward.
• Step 4: Check index 3 (value 7). Match found. Return index 3.

The search required 4 comparisons to locate the target element.

Algorithm and Pseudocode

Standard Linear Search

procedure LinearSearch(A, n, target) Input: A = array of n elements, target = value to find Output: index of target in A, or -1 if not found for i := 0 to n - 1 do if A[i] = target then return i end if end for return -1end procedure

Linear Search Returning All Occurrences

procedure LinearSearchAll(A, n, target) Input: A = array of n elements, target = value to find Output: list of all indices where target appears results := empty list for i := 0 to n - 1 do if A[i] = target then append i to results end if end for return resultsend procedure

Sentinel Linear Search

procedure SentinelLinearSearch(A, n, target) Input: A = array of n elements, target = value to find Output: index of target in A, or -1 if not found last := A[n - 1] A[n - 1] := target // Place sentinel i := 0 while A[i] != target do i := i + 1 end while A[n - 1] := last // Restore original value if i < n - 1 or A[n - 1] = target then return i else return -1 end ifend procedure

Complexity Analysis

Time Complexity

Space Complexity

O(1): Linear search uses only a constant amount of extra memory regardless of input size. It requires a single index variable and possibly a temporary variable for comparisons, making it extremely memory-efficient.

Comparison Count Analysis

If the target element is equally likely to be at any position in the array, the expected number of comparisons for a successful search is (n + 1) / 2. For an unsuccessful search, exactly n comparisons are always required. The sentinel variant reduces the number of comparisons per iteration from two (one for the element check and one for the bounds check) to one, yielding a practical speedup even though the asymptotic complexity remains O(n).

Worked Example

Search for target = 42 in the array A = [15, 3, 42, 27, 8, 19, 42, 55].

Step-by-Step Trace

Result: The target value 42 is found at index 2 after 3 comparisons. Note that the second occurrence at index 6 is not examined because the standard linear search returns the first match.

Unsuccessful Search Example

Search for target = 10 in the same array A = [15, 3, 42, 27, 8, 19, 42, 55].

The algorithm checks every element from index 0 through index 7, performing 8 comparisons without finding a match. It returns -1, indicating the element is not present in the array.

Sentinel Linear Search

The sentinel variant is an optimization of standard linear search that reduces the number of comparisons performed in the inner loop. In a standard linear search, each iteration of the loop performs two comparisons: one to check whether the current element matches the target, and one to check whether the end of the array has been reached. The sentinel technique eliminates the bounds check.

How the Sentinel Works

1. Save the last element of the array in a temporary variable.
2. Replace the last element with the target value (this is the "sentinel").
3. Search from the beginning of the array. Since the target is guaranteed to exist (as the sentinel), no bounds check is needed.
4. When a match is found, restore the original last element.
5. Check whether the match was the sentinel or a genuine occurrence.

This optimization roughly halves the number of instructions executed per iteration, providing a measurable speedup on large arrays even though the asymptotic time complexity remains O(n).

"The sentinel is a well-known programming trick: by storing a copy of the search key at the end of the array, we can eliminate the array-bounds check from the inner loop." -- Jon Bentley, Programming Pearls

Advantages and Disadvantages

Advantages

• Simplicity: Extremely easy to understand, implement, and debug. Minimal code is required.
• No Sorting Required: Works on unsorted arrays, linked lists, and any sequential data structure without preprocessing.
• Works on Any Data: Can search through any data type that supports equality comparison, including strings, objects, and composite types.
• Optimal for Small Collections: For very small arrays (fewer than 10-20 elements), the overhead of more complex algorithms outweighs their theoretical advantages.
• Works with Linked Lists: Unlike binary search, linear search works naturally with linked lists and other non-random-access data structures.
• No Extra Space: Uses O(1) auxiliary space, making it ideal for memory-constrained environments.

Disadvantages

• Slow for Large Datasets: O(n) time complexity makes it impractical for collections with thousands or millions of elements.
• Does Not Exploit Order: If the data is sorted, linear search wastes the opportunity to use faster algorithms like binary search.
• High Comparison Count: On average, half the elements must be examined for successful searches and all elements for unsuccessful ones.
• Poor Cache Behavior on Large Data: Scanning through very large arrays can cause frequent cache misses, degrading performance further.

Comparison with Other Search Algorithms

Linear search is the only algorithm in this table that works on completely unstructured, unsorted data without any preprocessing. While hash tables offer O(1) average lookup, they require O(n) space and time to build. Binary search is dramatically faster but requires sorted input. The choice of algorithm depends entirely on the context: data size, whether the data is sorted, how many searches will be performed, and memory constraints.

Applications

Unsorted Data

When data arrives in an arbitrary order and only a single lookup is needed, sorting the data first would cost O(n log n), making linear search the more efficient choice at O(n).

Small Collections

For arrays with fewer than about 20 elements, linear search often outperforms binary search due to lower overhead: no need for index calculations, and modern CPU branch prediction handles the simple loop efficiently.

Linked Lists

Linked lists do not support random access, so binary search cannot be applied directly. Linear search is the standard approach for searching through singly or doubly linked lists.

Searching with Complex Predicates

When searching based on arbitrary conditions (for example, finding the first record where multiple fields satisfy certain criteria), linear search is the natural choice because it simply applies the predicate to each element in turn.

Real-Time Systems

In certain real-time systems where predictability is more important than speed, linear search provides consistent, predictable performance without the variable-depth recursion of binary search or the potential hash collision chains of hash tables.

Text Editors and Search Tools

Finding a substring or pattern within a document is fundamentally a linear scan through characters. While optimized string matching algorithms (such as KMP or Boyer-Moore) reduce redundant comparisons, the basic approach is still sequential.

References

• Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. Introduction to Algorithms (3rd ed.). MIT Press, 2009. Chapter 2: Getting Started.
• Knuth, D. E. The Art of Computer Programming, Volume 3: Sorting and Searching (2nd ed.). Addison-Wesley, 1998. Section 6.1: Sequential Searching.
• Sedgewick, R. and Wayne, K. Algorithms (4th ed.). Addison-Wesley, 2011. Section 3.1: Symbol Tables.
• Bentley, J. Programming Pearls (2nd ed.). Addison-Wesley, 2000. Column 9: Code Tuning.