Linear Search Algorithm in DSA Typescript

Mental Model

Look at each item one by one until you find the one you want or reach the end.

Analogy: Imagine looking for a book on a shelf by checking each book from left to right until you find it.

Array: [3] -> [7] -> [1] -> [9] -> [5] -> null
Search for: 9
↑ (start here)

Dry Run Walkthrough

Input: array: [3, 7, 1, 9, 5], search value: 9

Goal: Find the position of 9 in the array or say it is not found

Step 1: Check first element 3

[3↑] -> [7] -> [1] -> [9] -> [5] -> null

Why: We start from the first element to see if it matches the search value

Step 2: Check second element 7

[3] -> [7↑] -> [1] -> [9] -> [5] -> null

Why: 3 is not 9, so move to next element

Step 3: Check third element 1

[3] -> [7] -> [1↑] -> [9] -> [5] -> null

Why: 7 is not 9, continue checking next

Step 4: Check fourth element 9

[3] -> [7] -> [1] -> [9↑] -> [5] -> null

Why: Found the search value 9 at this position

Result:

[3] -> [7] -> [1] -> [9↑] -> [5] -> null
Answer: Found 9 at index 3

Annotated Code

DSA Typescript

class LinearSearch {
  static search(arr: number[], target: number): number {
    for (let i = 0; i < arr.length; i++) {
      if (arr[i] === target) {
        return i; // found target at index i
      }
    }
    return -1; // target not found
  }
}

const array = [3, 7, 1, 9, 5];
const target = 9;
const result = LinearSearch.search(array, target);
if (result !== -1) {
  console.log(`Found ${target} at index ${result}`);
} else {
  console.log(`${target} not found in array`);
}

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

iterate over each element in the array

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

check if current element matches the target

return i; // found target at index i

stop and return index when target is found

return -1; // target not found

return -1 if target is not in the array after full scan

Output

Found 9 at index 3

Complexity Analysis

Time: O(n) because in the worst case we check every element once

Space: O(1) because we only use a few variables regardless of input size

vs Alternative: Compared to binary search which is O(log n), linear search is slower but works on unsorted arrays

Edge Cases

empty array

returns -1 immediately since there are no elements to check

DSA Typescript

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

target not in array

returns -1 after checking all elements

DSA Typescript

return -1; // target not found

target is first element

returns index 0 immediately

DSA Typescript

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

When to Use This Pattern

When you need to find an item in a list without any order, use linear search because it checks each item one by one.

Common Mistakes

Mistake: Stopping the search too early without checking all elements
Fix: Only stop when you find the target or finish checking all elements

Mistake: Returning index before confirming the element matches the target
Fix: Always check if arr[i] === target before returning index

Summary

It looks through each item in a list to find a target value.

Use it when the list is unsorted or small.

The key is to check each element one by one until you find the target.