0123456789
ALGO.ANIMATED · SEARCHING

Linear Search Explained with Animations

The simplest search algorithm — scan every element one by one. Watch linear search in action, learn when to use it, and compare it with binary search.

// WHAT YOU'LL LEARN

🔍Step-by-Step Scan
⚡O(n) Complexity
🛡️Sentinel Variant
🔄Recursive Version
⚖️Linear vs Binary
📋Flowchart & Pseudocode
Beginner·10 min·Algorithms / Searching
Reviewed by CodeTikki Academic Team

Prerequisites: Basic programming · Arrays · Loops

// DEFINITION

What is
linear search?

Linear search (also called sequential search) checks each element of an array one by one, from start to end, until it finds the target or reaches the end of the array.

It works on any array— sorted or unsorted. It's the simplest search algorithm, with O(n) time complexity.

FOUND — target = 7
5
3
8
1
7
Check 5 → not 7
Check 3 → not 7
Check 8 → not 7
Check 1 → not 7
Check 7 → FOUND at index 4!
✓ 5 comparisons → O(n) worst case
NOT FOUND — target = 6
5
3
8
1
7
Check 5 → not 6
Check 3 → not 6
Check 8 → not 6
Check 1 → not 6
Check 7 → not 6
✗ All 5 checked → return -1

// INTERACTIVE VISUALIZER

Watch it scan.

Set a target, press PLAY, and watch linear search check each element one by one. Try different targets — including ones not in the array!

5
3
8
1
9
4
7
2
6

Press PLAY to start searching!

Comparisons

0

Array Size

9

Result

—

// ALGORITHM WALKTHROUGH

Flowchart &
pseudocode.

// FLOWCHART · Linear Search
Step-by-step flowchart
arr=[5,3,8,1,7], target=7
YesNoYesNoloopStarti = 0i < n ?arr[i] ==target ?return ii = i + 1return -1End

Press PLAY to trace the algorithm through the flowchart.

0 / 9
// PSEUDOCODE · Linear Search
Pseudocode execution trace
arr=[5,3,8,1,7], target=7
1function linearSearch(arr, target):
2for i = 0 to n-1:
3if arr[i] == target:
4return i
5return -1

Press PLAY to step through the algorithm line by line.

0 / 12

// LINEAR VS BINARY

Linear vs
binary search.

Drag the slider to see how many comparisons each algorithm needs. Binary search requires sorted data — linear search works on anything.

n = 1,000

LINEAR SEARCH

1,000

comparisons (worst case)

BINARY SEARCH

10

comparisons (worst case)

For n=1,000, binary search is approximately 100× faster than linear search (on sorted data).

When to use Linear Search

  • Array is unsorted
  • Array is small (< 100 elements)
  • Searching a linked list
  • You only search once (sorting not worth it)
  • Finding all occurrences of a value

When to use Binary Search

  • Array is sorted
  • Array is large (1000+ elements)
  • You search the same array repeatedly
  • Random access is available (arrays, not linked lists)
  • O(log n) performance is needed

// OPTIMIZATION

Sentinel search.

Sentinel linear search is an optimization that removes the i < n bounds check from the loop. We place the target at the end of the array, so the loop is guaranteed to find it — we only need one comparison per iteration instead of two.

Standard: 2 checks/iteration

while (i < n) {        // check 1
  if (arr[i] == target) // check 2
    return i;
  i++;
}

Sentinel: 1 check/iteration

arr[n-1] = target;     // place sentinel
while (arr[i] != target) // only 1 check
  i++;
// check if real or sentinel

// RECURSIVE VARIANT

Recursive
linear search.

function recursiveSearch(arr, target, i):
  if i >= arr.length:        // base case: not found
    return -1
  if arr[i] == target:       // base case: found
    return i
  return recursiveSearch(arr, target, i + 1)  // recursive case

Pros

  • Elegant, concise code
  • Tail-recursive (can be optimized by compiler)
  • Good for teaching recursion

Cons

  • O(n) space (call stack)
  • Stack overflow on large arrays
  • Slower than iterative (function call overhead)

// COMPLEXITY ANALYSIS

Complexity
summary.

CaseTime ComplexityComparisonsDescription
BestO(1)1Target at first position
AverageO(n)n/2Target in the middle
Worst (found)O(n)nTarget at last position
Worst (not found)O(n)nTarget not in array
SpaceO(1)—No extra data structures

// PRACTICE & ASSESS

Test your understanding

Now that you've learned the concept, put it into practice. Solve coding problems and take quizzes to reinforce what you've learned.

💻

Coding Problems

The First Scan: Find an Element in an ArrayL1The Index Finder: Return the Position of a TargetL1The Missing Element: Search and Return -1 if Not FoundL2The Count Occurrences: Find All Instances of a ValueL3The Sentinel Search: Optimize with SentinelL4The Recursive Search: Implement Linear Search RecursivelyL4The Bidirectional Search: Search from Both EndsL5The Min/Max Finder: Find Minimum and Maximum in One PassL5The Move-to-Front: Implement Self-Organizing ListL7The Search in Rotated Array: Linear ApproachL6

// TUTORIAL QUIZZES · LEVELS 1–9

Test your mastery

Nine progressive quizzes from Level 1 to Level 9. Each has 10 questions with a 10-minute timer. XP scales with level — L1 gives 10 XP, L9 gives 90 XP. Click a quiz to expand and begin.

// REFERENCES

Sources & further reading

  1. [1]
    Introduction to Algorithms (CLRS)T. H. Cormen et al. — Chapter 2: linear search as a introductory example
  2. [2]
    The Art of Computer Programming, Vol. 3Donald Knuth — Section 6.1: sequential searching
  3. [3]
    AlgorithmsRobert Sedgewick & Kevin Wayne — elementary searching methods
  4. [4]
    Self-Organizing Sequential Search HeuristicsJ. L. Bentley & C. C. McGeoch — Communications of the ACM (1985)
  5. [5]
    Programming PearlsJon Bentley — Column 2: search algorithms and correctness

// READY?

Master algorithms
with CodeTikki.

Practice 1,000+ coding problems, follow career roadmaps, and get hired.