Linear Search

searching · O(n)

5

Configure inputs and press Visualize to begin.

64
0
34
1
25
2
12
3
22
4
11
5
90
6
45
7
Default
Comparing
Swap
Pivot
Sorted
Found
Pseudocode & Implementations
2 approaches

Sequentially scan every element. Works on unsorted data.

LINEAR-SEARCH(A, target):
  FOR i = 0 TO length(A)-1:
    IF A[i] == target:
      RETURN i    // found at index i
  RETURN -1       // not found
Complexity Analysis

Time Complexity

Best Case
ConstantO(1)
Average
LinearO(n)
Worst Case
LinearO(n)
Space (aux)
ConstantO(1)
sequentialsimple
About

Sequentially checks each element until the target is found or the end is reached. No preprocessing required.

Key Insight

Simple and works on any collection, sorted or unsorted.

Use Cases

Small unsorted arraysLinked listsSimple lookups