Linear Search

Category: Classical
Difficulty: Beginner
Time Complexity: O(n)
Space Complexity: O(1)

Overview

Linear Search is the simplest way to find a value in a collection: examine each element in turn until the target is found or the array is exhausted. Unlike Binary Search it does not require the array to be sorted, which makes it the go-to method for unsorted data, linked lists, and small inputs. Its O(n) time is the cost of that generality — every element may need to be checked in the worst case.

Try It

• Web: Open in Eigenvue →
• Python:

  import eigenvue
  eigenvue.show("linear-search")

Default Inputs

{
  "array": [
    7,
    2,
    9,
    4,
    1,
    8,
    3
  ],
  "target": 4
}

Input Examples

Default (target found)

{
  "array": [
    7,
    2,
    9,
    4,
    1,
    8,
    3
  ],
  "target": 4
}

Target not found

{
  "array": [
    7,
    2,
    9,
    4,
    1,
    8,
    3
  ],
  "target": 5
}

Target is first element

{
  "array": [
    3,
    1,
    4,
    1,
    5
  ],
  "target": 3
}

Target is last element

{
  "array": [
    3,
    1,
    4,
    1,
    5
  ],
  "target": 5
}

Duplicate target (returns first)

{
  "array": [
    5,
    1,
    5,
    2,
    5
  ],
  "target": 5
}

Code

Pseudocode

function linearSearch(array, target):
  for i = 0 to length(array) - 1:
    if array[i] == target:
      return i
  return -1

Python

def linear_search(array: list[int], target: int) -> int:
    for i in range(len(array)):
        if array[i] == target:
            return i
    return -1

JavaScript

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

Key Concepts

No Sorting Required

Linear Search works on any array, sorted or not. This is its key advantage over Binary Search, which only works on sorted data.

First Match Wins

The scan returns the index of the first element equal to the target. If duplicates exist, later occurrences are never reached.

Worst and Best Cases

Best case is O(1) when the target is the first element; worst case is O(n) when the target is last or absent, requiring every element to be checked.

Common Pitfalls

• Using it on large sorted data: If the data is already sorted and large, Binary Search’s O(log n) is dramatically faster. Reach for Linear Search only when the data is unsorted or small.
• Forgetting the not-found case: A correct implementation must return a sentinel (like -1) when the loop finishes without a match, rather than falling through with an undefined result.

Quiz

Q1: Does Linear Search require the array to be sorted?

• A) Yes
• B) No
• C) Only for numbers
• D) Only for large arrays

Show answer

Answer: B) No

Linear Search checks every element in order, so it works on unsorted data — no sorting is needed.

Q2: What is the worst-case time complexity of Linear Search?

• A) O(1)
• B) O(log n)
• C) O(n)
• D) O(n²)

Show answer

Answer: C) O(n)

In the worst case (target absent or last), all n elements are examined, giving O(n).

Q3: If the target appears multiple times, which index does Linear Search return?

• A) The last one
• B) The first one
• C) A random one
• D) All of them

Show answer

Answer: B) The first one

The scan stops at the first element equal to the target and returns that index.

Further Reading

• Linear Search — Wikipedia (reference)

Related Algorithms

• Binary Search
• Bubble Sort