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.

Practice

1. What is the main idea behind the Linear Search Algorithm?

easy

A. Check each element one by one until the target is found or list ends

B. Divide the list into halves repeatedly to find the target

C. Sort the list first then search using binary steps

D. Use a hash table to find the target instantly

Solution

1. Step 1: Understand linear search process

   Linear search checks each element in order, from start to end.

2. Step 2: Compare with other search methods

   Binary search divides list, hash uses extra memory, linear is simple sequential check.

3. Final Answer:

   Check each element one by one until the target is found or list ends -> Option A

4. Quick Check:

   Linear search = sequential check [OK]

Hint: Linear search checks items one by one [OK]

Common Mistakes:

• Confusing linear search with binary search
• Thinking linear search requires sorted list
• Assuming linear search uses extra memory

2. Which of the following is the correct syntax to start a linear search loop in JavaScript for an array arr?

easy

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

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

C. for (let i = 1; i < arr.length; i++)

D. for (let i = 1; i <= arr.length; i++)

Solution

1. Step 1: Understand array indexing in JavaScript

   Arrays start at index 0 and go up to length - 1.

2. Step 2: Choose loop condition to avoid out-of-bound error

   Loop must run while i is less than arr.length, not equal or greater.

3. Final Answer:

   for (let i = 0; i < arr.length; i++) -> Option B

4. Quick Check:

   Loop runs from 0 to length-1 [OK]

Hint: Use i < arr.length to avoid index errors [OK]

Common Mistakes:

• Using <= instead of < causing out-of-bound errors
• Starting loop from 1 instead of 0
• Confusing array length with last index

3. What will be the output of the following code?

const arr = [4, 8, 15, 16, 23, 42];
function linearSearch(array, target) {
  for (let i = 0; i < array.length; i++) {
    if (array[i] === target) {
      return i;
    }
  }
  return -1;
}
console.log(linearSearch(arr, 15));

medium

A. 2

B. 3

C. -1

D. 15

Solution

1. Step 1: Trace the loop to find target 15

   Indices: 0=4, 1=8, 2=15. At i=2, array[i] === 15 is true.

2. Step 2: Return index when target found

   Function returns 2 immediately when target matches.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   Index of 15 in array = 2 [OK]

Hint: Return index when target matches during loop [OK]

Common Mistakes:

• Returning value instead of index
• Returning -1 even if target exists
• Off-by-one errors in index

4. Find the error in this linear search function and choose the correct fix:

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

medium

A. Initialize i to 1 instead of 0

B. Change == to === in if condition

C. Change loop condition to i < arr.length

D. Add a break statement after return

Solution

1. Step 1: Identify loop condition error

   Loop runs while i <= arr.length, which causes out-of-bound access at i = arr.length.

2. Step 2: Fix loop condition to prevent error

   Change condition to i < arr.length to stay within valid indices.

3. Final Answer:

   Change loop condition to i < arr.length -> Option C

4. Quick Check:

   Loop must stay within array bounds [OK]

Hint: Use i < arr.length to avoid index errors [OK]

Common Mistakes:

• Using <= instead of < in loop condition
• Thinking == vs === causes runtime error here
• Adding break after return (unnecessary)

5. You want to find the first occurrence of the number 7 in the array [3, 5, 7, 7, 9] using linear search. Which code snippet correctly returns the index of the first 7?

hard

A. for (let i = arr.length - 1; i >= 0; i--) { if (arr[i] === 7) return i; } return -1;

B. for (let i = 0; i < arr.length; i++) { if (arr[i] == 7) return arr[i]; } return -1;

C. for (let i = 1; i <= arr.length; i++) { if (arr[i] === 7) return i; } return -1;

D. for (let i = 0; i < arr.length; i++) { if (arr[i] === 7) return i; } return -1;

Solution

1. Step 1: Understand requirement to find first occurrence

   Start from index 0 and return index when first 7 is found.

2. Step 2: Analyze each option for correctness

   for (let i = 0; i < arr.length; i++) { if (arr[i] === 7) return i; } return -1; loops forward, returns index correctly. for (let i = arr.length - 1; i >= 0; i--) { if (arr[i] === 7) return i; } return -1; loops backward (last occurrence). for (let i = 1; i <= arr.length; i++) { if (arr[i] === 7) return i; } return -1; has wrong loop bounds. for (let i = 0; i < arr.length; i++) { if (arr[i] == 7) return arr[i]; } return -1; returns value, not index.

3. Final Answer:

   for (let i = 0; i < arr.length; i++) { if (arr[i] === 7) return i; } return -1; -> Option D

4. Quick Check:

   Forward loop returns first match index [OK]

Hint: Loop forward and return index on first match [OK]

Common Mistakes:

• Looping backward returns last occurrence, not first
• Returning value instead of index
• Using wrong loop bounds causing errors