Linear Search Algorithm

What Is Linear Search?

Linear search is a simple searching algorithm that checks each element in a collection one at a time until the required value is found or all elements have been examined.

It is also called sequential search because the elements are inspected sequentially. Linear search does not require the array to be sorted, which makes it useful when working with small or unsorted collections.

How Linear Search Works

Suppose we have the following array and want to find the value 42:

[15, 8, 27, 42, 63]

Linear search starts at the first element and compares each value with the target.

Target = 42

15 === 42  → No
 8 === 42  → No
27 === 42  → No
42 === 42  → Yes

Target found at index 3.

Once the target is found, the algorithm can stop immediately instead of checking the remaining elements.

Steps of the Linear Search Algorithm

A basic linear search follows a straightforward sequence of operations:

1. Start from the first element of the array.
2. Compare the current element with the target value.
3. If they match, return the current index or required result.
4. If they do not match, move to the next element.
5. Continue until the target is found or the array ends.
6. Return a value such as -1 if the target does not exist.

Linear Search Example

Consider this array:

const numbers = [23, 11, 45, 17, 89, 34];

Target = 89

The algorithm examines the values in this order:

23 → not found
11 → not found
45 → not found
17 → not found
89 → found

The target is found at index 4.

Linear Search Algorithm

The logic can be represented using simple pseudocode:

linearSearch(array, target)

for each index from 0 to array.length - 1
    if array[index] equals target
        return index

return -1

The algorithm does not need additional data structures. It simply keeps track of the current position while scanning the array.

Linear Search Implementation in JavaScript

A basic JavaScript implementation can return the index of the first matching element:

function linearSearch(array, target) {
  for (let i = 0; i < array.length; i++) {
    if (array[i] === target) {
      return i;
    }
  }

  return -1;
}

const numbers = [23, 11, 45, 17, 89, 34];

console.log(linearSearch(numbers, 89));
// 4

console.log(linearSearch(numbers, 100));
// -1

Why Does Linear Search Work on Unsorted Arrays?

Linear search does not make assumptions about the order of elements. It examines each element independently and compares it directly with the target.

[42, 7, 91, 18, 3, 65]

Even though this array is not sorted, linear search can still find any existing value. This is one of the main reasons the algorithm is useful for general-purpose searching.

Best Case, Average Case, and Worst Case

The running time of linear search depends on the position of the target element.

Best Case: O(1)

The best case occurs when the target is the first element. Only one comparison is required.

[42, 10, 20, 30, 40]

Target = 42

One comparison → Found

Average Case: O(n)

In the average case, the target may appear somewhere around the middle of the collection, requiring a number of comparisons proportional to the array size.

Worst Case: O(n)

The worst case occurs when the target is the last element or does not exist at all. The algorithm must inspect every element.

Space Complexity of Linear Search

The iterative version of linear search uses only a small number of variables in addition to the input array. Therefore, its auxiliary space complexity is O(1).

Time Complexity:
Worst case → O(n)

Space Complexity:
O(1)

Linear Search With Duplicate Values

An array can contain the same value more than once. A standard linear search that returns immediately will find only the first occurrence.

const numbers = [10, 25, 10, 40, 10];

Target = 10

First occurrence:
index 0

If an application needs every occurrence, the search must continue after a match is found.

function findAllOccurrences(array, target) {
  const indexes = [];

  for (let i = 0; i < array.length; i++) {
    if (array[i] === target) {
      indexes.push(i);
    }
  }

  return indexes;
}

const numbers = [10, 25, 10, 40, 10];

console.log(findAllOccurrences(numbers, 10));
// [0, 2, 4]

Linear Search With Objects

Linear search can also be applied to arrays containing objects. Instead of comparing the entire object, the algorithm can compare a specific property.

const products = [
  { id: 101, name: "Keyboard" },
  { id: 102, name: "Mouse" },
  { id: 103, name: "Monitor" }
];

function findProduct(products, productId) {
  for (let i = 0; i < products.length; i++) {
    if (products[i].id === productId) {
      return products[i];
    }
  }

  return null;
}

console.log(findProduct(products, 102));
// { id: 102, name: "Mouse" }

Linear Search With a Custom Condition

Searching does not always mean looking for an exact value. The same sequential approach can be used to find the first element that satisfies a condition.

function findFirstGreaterThan(array, target) {
  for (let i = 0; i < array.length; i++) {
    if (array[i] > target) {
      return i;
    }
  }

  return -1;
}

const numbers = [12, 18, 7, 25, 31];

console.log(findFirstGreaterThan(numbers, 20));
// 3

This is still a linear scan because elements are examined sequentially until a matching condition is found.

Linear Search and Early Termination

One useful property of linear search is that it can stop as soon as the required result is known. This avoids unnecessary comparisons.

[5, 12, 19, 27, 34, 41]

Target = 19

5  → no
12 → no
19 → found

27, 34, and 41 do not need to be checked.

Early termination does not change the worst-case O(n) complexity, but it can reduce the actual number of comparisons for successful searches.

Linear Search on an Empty Array

When the array is empty, there are no elements to examine. A correctly implemented search should immediately return the not-found result.

const numbers = [];

console.log(linearSearch(numbers, 10));
// -1

Linear Search vs Binary Search

Linear search and binary search solve the same general problem but use different strategies.

When Should You Use Linear Search?

Linear search is particularly useful when the collection is small, unsorted, or searched only occasionally. Its simple implementation can also make it preferable when the overhead of maintaining a more complex search structure is unnecessary.

• The array is unsorted.
• The number of elements is relatively small.
• Searches are infrequent.
• The data changes frequently and maintaining sorted order is undesirable.
• A simple implementation is more appropriate than a specialized search algorithm.

When Linear Search May Not Be Suitable

Repeatedly scanning a very large collection can become expensive because each unsuccessful search may inspect every element. If the data is already sorted and many searches are required, a different searching strategy may reduce the number of comparisons.

The choice should consider the complete workload rather than the search operation alone. Data ordering, update frequency, collection size, and number of searches all influence the appropriate approach.

Common Linear Search Mistakes

• Returning the wrong index after finding the target.
• Forgetting to return a not-found result.
• Continuing the search unnecessarily after finding the first required match.
• Assuming the array must be sorted.
• Using the wrong comparison condition for object-based searches.
• Confusing O(1) indexed access with O(n) searching for an unknown value.
• Using linear search repeatedly on very large collections without considering the workload.

Linear Search in Real Applications

Linear search appears in many everyday programming tasks. Examples include checking whether a small list contains a particular value, finding a user in a small in-memory collection, locating the first matching configuration item, or scanning records until a condition is satisfied.

Even when developers use built-in methods such as find() or indexOf(), the underlying operation for an unsorted array is commonly a sequential search.

Key Takeaways

• Linear search checks elements sequentially.
• It works with both sorted and unsorted arrays.
• The algorithm can stop immediately when the required element is found.
• The best-case time complexity is O(1).
• The average and worst-case time complexity are O(n).
• The iterative algorithm uses O(1) auxiliary space.
• A standard implementation can return the first matching index.
• Finding all occurrences requires scanning the entire array.
• Binary search can provide faster searching for appropriately sorted data.