Suggest an edit

Improve this article

Refine the answer for “How to find an element in an array using linear search?”. Your changes go to moderation before they’re published.

Approval required

Content

What you’re changing

Title (EN)

Short answer (EN)

Shown above the full answer for quick recall.

Answer (EN)

## Short answer

Linear search is a sequential scan of an array from left to right, comparing each element with the target value. As soon as the element is found, we return its index; if the whole array was scanned without a match, we return -1. Time: O(n), memory: O(1).

```js
function linearSearch(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) return i; // early exit
  }
  return -1; // not found
}

console.log(linearSearch([4, 2, 7, 2], 7)); // 2
console.log(linearSearch([4, 2, 7, 2], 5)); // -1
```

## Detailed breakdown

### Algorithm idea

1. Walk the array from start to end over indices i = 0..n-1.
2. Compare arr[i] with the target value (or check a predicate).
3. If the condition holds, return i (or the element itself).
4. If the end is reached, the element is not present (return -1/undefined per the function's contract).

## Complexity

- Time: O(n) in the worst and average cases; O(1) in the best case (if the element is first).
- Memory: O(1), just a counter/index.
- Stability: finds the first occurrence (if you need "all", you need to collect indices).

## Code examples

### Searching for a number (returning the index)

```js
function linearSearch(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) return i;
  }
  return -1;
}

console.log(linearSearch([10, 20, 30], 20)); // 1
console.log(linearSearch([10, 20, 30], 25)); // -1
```

### Searching by predicate (objects)

Useful when the comparison is not a simple ===, but by a field/condition.

```js
// Returns the index of the first element satisfying the predicate
function linearSearchBy(arr, predicate) {
  for (let i = 0; i < arr.length; i++) {
    if (predicate(arr[i], i, arr)) return i;
  }
  return -1;
}

const users = [
  { id: 1, name: 'Alice' },
  { id: 2, name: 'Bob' },
  { id: 3, name: 'Alice' }
];

const idx = linearSearchBy(users, (u) => u.name === 'Alice');
console.log(idx); // 0 (first occurrence)
```

### Finding all occurrences

```js
function linearSearchAll(arr, predicate) {
  const indices = [];
  for (let i = 0; i < arr.length; i++) {
    if (predicate(arr[i], i, arr)) indices.push(i);
  }
  return indices; // [] if nothing was found
}

console.log(linearSearchAll([1, 2, 3, 2, 2], (x) => x === 2)); // [1, 3, 4]
```

### Last occurrence (scan right to left)

```js
function linearSearchLast(arr, target) {
  for (let i = arr.length - 1; i >= 0; i--) {
    if (arr[i] === target) return i;
  }
  return -1;
}

console.log(linearSearchLast([1, 2, 3, 2, 2], 2)); // 4
```

## Edge cases and practical nuances

- Empty array: return -1 immediately.
- Duplicates: the classic variant returns the first occurrence. If you need the last one, scan from the right (example above).
- === comparison: for reference types, references are compared, not "content". For objects, use a key-by-key comparison or a predicate.
- NaN in JavaScript: NaN !== NaN, so a plain === will not find NaN. Add a Number.isNaN check.
- String case: for case-insensitive search, normalize both sides (toLowerCase() / localeCompare).

```js
// Search with NaN support and case-insensitivity for strings
function linearSearchSafe(arr, target) {
  const isStr = typeof target === 'string';
  const normTarget = isStr ? target.toLowerCase() : target;

for (let i = 0; i < arr.length; i++) {
    const val = arr[i];
    if (isStr && typeof val === 'string') {
      if (val.toLowerCase() === normTarget) return i;
    } else if (Number.isNaN(target) && Number.isNaN(val)) {
      return i; // both NaN
    } else if (val === target) {
      return i;
    }
  }
  return -1;
}

console.log(linearSearchSafe(['a', 'B', 'c'], 'b')); // 1
console.log(linearSearchSafe([1, NaN, 3], NaN));      // 1
```

## When to use linear search

- Small arrays or a one-off search over small volumes of data.
- The data set is unsorted and it is not worth spending resources on sorting/indexing.
- Streaming data, where access is sequential only.
- If search is frequent and the data is large/static, consider sorting + binary search or indexes (Map/Set).

## Pseudocode

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

Markdown · drag & drop images · ⌘B / ⌘I shortcuts694 words

For the reviewer

Note to the moderator (optional)

Visible only to the moderator. Helps review go faster.