Back to Study Material Data Structures and Algorithms

Linear Search

Linear search is the simplest searching algorithm you will ever encounter. It works by scanning every element in a list one by one, starting from the first...

Linear Search

How Linear Search Works

Linear search is the simplest searching algorithm you will ever encounter. It works by scanning every element in a list one by one, starting from the first element, until either the target value is found or the entire list has been checked. Because it makes no assumptions about the order of the data, it works equally well on sorted and unsorted arrays.

Consider a list of seven numbers: 14, 3, 27, 9, 51, 6, 33. If you are searching for the value 51, the algorithm checks 14 first (not a match), then 3, then 27, then 9, and finally reaches 51 at index 4 and returns that position. If the value does not exist, the algorithm returns a sentinel value like -1 after exhausting every element.

The pseudocode is straightforward. For each index i from 0 to n-1, compare the element at index i to the target. If they match, return i. If the loop ends without a match, return -1.

Time complexity is O(1) in the best case when the target is the first element, O(n) on average when the target sits somewhere in the middle, and O(n) in the worst case when the target is last or absent. Space complexity is O(1) because no extra memory is allocated beyond a few variables.

Linear search becomes genuinely useful when the dataset is small, unsorted, or stored in a structure that does not allow random access such as a singly linked list. It is also the only option when the data arrives in a stream and cannot be preprocessed.

One worked example worth remembering: imagine an array of student names stored in the order they enrolled. Because enrollment order has nothing to do with alphabetical order, a binary search is impossible, and linear search is the natural tool.

Interview tip: if an interviewer asks you to search an unsorted array with a single query, state clearly that linear search at O(n) is optimal because any algorithm must inspect every element at least once in the worst case.

Variations and Optimizations

Although linear search is simple, several practical optimizations are worth knowing. The sentinel optimization places the target value at the end of the array before starting the loop. This eliminates the boundary check on each iteration because the loop is guaranteed to terminate when it hits the sentinel, reducing the constant factor of the inner loop by roughly half on many architectures.

Another variant is the transposition heuristic, also called the move-to-front rule. Every time a successful search finds an element, that element is swapped one position closer to the front of the array. Over many repeated queries, frequently requested items migrate toward the beginning, improving average-case performance without any preprocessing.

A third variant applies to sorted arrays where you know the data is ordered. In this case you can terminate the search early as soon as the current element exceeds the target, because no later element can possibly match. This does not change the worst-case complexity, which remains O(n), but it cuts the average number of comparisons roughly in half on data that follows a uniform distribution.

Parallel linear search is a less commonly discussed technique that divides the array into k segments and searches each segment concurrently using k threads. The theoretical speedup is k times faster in the best case, though thread-creation overhead makes this worthwhile only for very large arrays.

Time complexity summary: best case O(1), average case O(n/2) simplified to O(n), worst case O(n). All variants share O(1) space complexity except parallel search, which needs O(k) auxiliary space for thread metadata.

Interview tip: when discussing linear search in an interview, mention the sentinel trick as a sign that you think about constant-factor optimizations and not just asymptotic complexity. Interviewers appreciate candidates who connect theory to practical implementation details.

When to Choose Linear Search

Choosing the right search algorithm is a matter of understanding your data and your constraints. Linear search earns its place in a programmer's toolkit for several concrete scenarios where more sophisticated algorithms would either be impossible or wasteful.

The first scenario is unsorted, dynamic data. If elements are added and removed frequently and there is no time to maintain a sorted order or a balanced tree, linear search is the pragmatic choice. The overhead of keeping data sorted often outweighs the search speedup gained from binary search unless search operations vastly outnumber insertions.

The second scenario involves tiny arrays, typically those with fewer than around 16 elements. Modern CPUs load contiguous memory into cache lines, and iterating through a small array is so fast in practice that the overhead of computing midpoints, handling recursion, or traversing tree pointers makes binary search or hash lookups slower in wall-clock time, even though their asymptotic complexity is better.

The third scenario is hardware or language constraints. In embedded systems with limited instruction sets, or in certain functional programming environments, index-based random access may be unavailable or expensive, making a sequential pass the only sensible approach.

A worked example from competitive programming illustrates this well. If you have an array of at most 100 integers and need to answer a single membership query, writing a linear scan takes 30 seconds to code and runs in well under a millisecond. Implementing a hash set for the same task takes several minutes to write and tests nothing additional about your algorithmic thinking.

Interview tip: never dismiss linear search as naive in an interview without first asking about the size of the input and whether the data is sorted. Demonstrating that you think about context before jumping to a complex solution signals strong engineering judgment.