DSA-VerseLearn by watching code run
DashboardData StructuresAlgorithmsVisualizerCORECoding PlaygroundInterview QuestionsComplexity AnalyzerLearning NotesBookmarksLearning ProgressSettings
Searching algorithms

Searching

Linear Search

Checks every element from left to right until the target is found or the array ends. Works on unsorted data.

Worst O(n)Space O(1)
Open visualizer

1Detailed explanation

Linear search checks each element in order until it finds the target or reaches the end. It needs no preparation and works on unsorted data, linked lists and streams.

Its cost grows linearly with the input: doubling the data doubles the worst-case work. For repeated searches on large static data, sorting once and using binary search, or building a hash set, is usually better.

2Pseudocode

procedure linearSearch(A, target)
  for i ← 0 to length(A) − 1
    if A[i] = target
      return i
  return −1

3Interactive visualization

Linear Searchinteractive Open full visualizer
7
3
9
4
1
8
0
1
2
3
4
5
ComparingSwapping / movingCurrentSorted / finalFound / placed

Checks every element from left to right until the target is found or the array ends. Works on unsorted data.

1 / 10

4Implementations

Equivalent implementations in four languages — the same code the visualizer highlights line by line. Each is a complete program.

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

const arr = [7, 3, 9, 4, 1, 8];
const target = 4;
console.log("Index of", target, "=", linearSearch(arr, target));

5Time and space complexity

Time
Best caseO(1)
Average caseO(n)
Worst caseO(n)
Space
AuxiliaryO(1)
InputO(n)
TotalO(n)

Time: Best case: the target is the first element (1 comparison). Worst case: the target is last or absent, so all n elements are compared. On average about n/2 comparisons → O(n).

Space: Only the loop index i is stored → O(1) auxiliary space.

6Common interview variations

  • Return every index where the target occurs.
  • Find the first and last occurrence in one pass.
  • Sentinel linear search (avoids the bounds check in the loop).
  • Search in a 2-D matrix row by row.

On this page

  1. 01Detailed explanation
  2. 02Pseudocode
  3. 03Interactive visualization
  4. 04Implementations (JS · Python · Java · Go)
  5. 05Time and space complexity
  6. 06Common interview variations