Comparisonsso far

Targetlooking for

Resultoutcome

—

Best / Worsttime

O(1) / O(n)

Array

Amber = current index · Emerald = found · dimmed = already checked

i = 0

41[0]

7[1]

68[2]

23[3]

91[4]

14[5]

56[6]

32[7]

84[8]

3[9]

75[10]

19[11]

Legend:currentfoundchecked

1 / 9

Speed

INITStep 1

Begin linear scan for target = 56 in an array of 12 elements. Walk left-to-right; stop at the first match. Worst case: 12 comparisons.

Target

linear-search.js

1function linearSearch(arr, target) {

2 for (let i = 0; i < arr.length; i++) {

3 if (arr[i] === target) {

4 return i; // found

5 }

6 }

8 return -1; // not found

Linear vs. Binary Search

Same values, same target — binary search first sorts the data, then eliminates half the remaining range per comparison.

Open Binary Search →

Linear Search

O(n)

Works on any array. Scans left-to-right and can stop early.

Comparisons 7Result 6

Binary Search

O(log n)

Requires sorted data. Halves the search range after every comparison.

Comparisons 4Sorted copy yes

Why binary wins at scale: Linear search may inspect every item. Once data is sorted, binary search needs at most ⌈log₂(n+1)⌉ comparisons — about 20 for one million elements.

How Linear Search Works

1. Start at index 0

Compare the first element with the target. If it matches, return immediately.

2. Move right

When the values differ, advance i by one and inspect the next element.

3. Stop or exhaust

Return the first matching index, or −1 after every element has been checked.

Linear search needs no preprocessing and works on unsorted data. For repeated lookups, sorting once and using binary search can reduce each search from O(n) to O(log n).

About the Linear Search algorithm

Check every element until a match is found. Works on unsorted data; baseline for search algorithm comparisons.

Category: Searching
Difficulty: Easy
Time complexity: O(n)
Space complexity: O(1)