What is linear search?

AlgorithmsJunior~2 min read

Short answer

Linear search is a simple algorithm for finding an element in an array (or list) that checks each element in sequence from the beginning to the end, until it finds the target or has gone through all elements.

Works on unsorted data.
Time: O(n), memory: O(1).
Returns the index of the found element (or -1/false if not found).

Detailed answer

Definition and idea

Linear search (sequential search) compares the target element with each element of the data structure in turn. It does not require prior sorting and works for arbitrary collections, including streaming or linked lists.

Algorithm (steps)

Start with the first element.
Compare the current element with the target.
If it matches, return its position/value.
Otherwise move to the next element and repeat until the end.
If the elements run out, report that it was not found.

Complexity

Time: O(n) on average and in the worst case (scanning the whole array); O(1) in the best case (the first element matches).
Memory: O(1) - needs virtually no extra memory.

When to use it

The data is unsorted and sorting is not worthwhile.
Small arrays, or few search queries are performed.
Data arrives as a stream (iterative access), for example a linked list.
You just need to check whether an element is present (predicate search).

Pseudocode

text

function linear_search(A, target):
  for i from 0 to length(A) - 1:
    if A[i] == target:
      return i
  return -1

Implementation: JavaScript

javascript

// Returns the index of the found element or -1
function linearSearch(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (Object.is(arr[i], target) || arr[i] === target) { // correctly handles NaN
      return i;
    }
  }
  return -1;
}

// Variant that returns a boolean
function includesLinear(arr, target) {
  return linearSearch(arr, target) !== -1;
}

// Variant with a predicate (more flexible for objects)
function findIndexLinear(arr, predicate) {
  for (let i = 0; i < arr.length; i++) {
    if (predicate(arr[i], i, arr)) return i;
  }
  return -1;
}

function findLinear(arr, predicate) {
  const idx = findIndexLinear(arr, predicate);
  return idx === -1 ? undefined : arr[idx];
}

Usage example

javascript

const nums = [5, 2, 9, 1, 5, 6];
console.log(linearSearch(nums, 9));   // 2
console.log(linearSearch(nums, 7));   // -1
console.log(includesLinear(nums, 1)); // true

const users = [
  { id: 10, name: 'Ana' },
  { id: 20, name: 'Ben' },
  { id: 30, name: 'Cat' },
];

const idxBen = findIndexLinear(users, u => u.name === 'Ben');
console.log(idxBen); // 1

const user30 = findLinear(users, u => u.id === 30);
console.log(user30); // { id: 30, name: 'Cat' }

Step-by-step illustration

Searching for 5 in [3, 4, 5, 2]: compare in order: 3 (no), 4 (no), 5 (yes) - return index 2.

Edge cases and nuances

Duplicates: the first matching index is usually returned.
Comparison in JS: Object.is correctly handles NaN and distinguishes +0/-0; combining Object.is || === covers the main cases.
Early exit: the loop stops as soon as the element is found (best-case performance).
Searching by object: use a predicate/comparator rather than reference comparison if you need to compare by a field.
For very large datasets and frequent queries, it is more efficient to build an index (Map/Set) in advance, or sort the data and use binary search.

Comparison with binary search

Requirement on the data: linear - any; binary - sorted only.
Complexity: O(n) vs O(log n) per search; but binary search has the cost of sorting, O(n log n), and of maintaining order on changes.
Choice: for a one-off search over an unsorted array, linear search is simpler and sometimes faster due to smaller constants.

Test cases

javascript

console.assert(linearSearch([], 1) === -1);
console.assert(linearSearch([1], 1) === 0);
console.assert(linearSearch([2, 3, 4], 1) === -1);
console.assert(linearSearch([2, 3, 1, 4], 1) === 2);
console.assert(linearSearch([NaN], NaN) === 0);
console.assert(findIndexLinear([{a:1},{a:2}], o => o.a === 2) === 1);

Short Answer

Interview ready

Premium

A concise answer to help you respond confidently on this topic during an interview.