Linear Search Algorithm in DSA Javascript

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.

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

Dry Run Walkthrough

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

Goal: Find the position of value 1 in the array or say not found

Step 1: Check first element 5

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

Why: Start from the beginning to find the value

Step 2: Move to second element 3

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

Why: 5 is not 1, so check next

Step 3: Move to third element 7

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

Why: 3 is not 1, continue searching

Step 4: Move to fourth element 1

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

Why: Found the value 1 at this position

Result:

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

Annotated Code

DSA Javascript

class LinearSearch {
  static search(arr, target) {
    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 = [5, 3, 7, 1, 9];
const target = 1;
const index = LinearSearch.search(array, target);
if (index !== -1) {
  console.log(`Found value ${target} at index ${index}`);
} else {
  console.log(`Value ${target} not found`);
}

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

Output

Found value 1 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 data

Edge Cases

empty array

returns -1 immediately because there is nothing to search

DSA Javascript

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

target not in array

returns -1 after checking all elements

DSA Javascript

return -1; // target not found

target is first element

returns index 0 immediately

DSA Javascript

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: Make sure to only stop when the target is found or after checking all elements

Summary

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

Use it when the list is small or not sorted.

The key is checking items one by one until you find the target or reach the end.