Linear Search Algorithm in DSA Javascript - Execution Trace

Concept Flow - Linear Search Algorithm

Start at index 0

↓

Check if element at index == target?

Yes→Return index

No↓

Move to next index

↓

Reached end of array?

Yes→Return -1 (not found)

↩Back to check element

Start from the first element, check each one for the target. If found, return index. If end reached without finding, return -1.

Execution Sample

DSA Javascript

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

Searches array elements one by one to find the target value and returns its index or -1 if not found.

Execution Table

Step	Operation	Index Checked	Element at Index	Is Element == Target?	Action	Result
1	Check element	0	3	No	Move to next index	Continue searching
2	Check element	1	5	No	Move to next index	Continue searching
3	Check element	2	7	Yes	Return index 2	Found target at index 2
4	End	-	-	-	-	Search stops

💡 Target found at index 2, so search stops early.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	Final
i	0	1	2	-	2
arr[i]	3	5	7	-	7
Result	undefined	undefined	2	-	2

Key Moments - 3 Insights

Why does the search stop immediately when the target is found?

Because in step 3 of the execution_table, the condition 'arr[i] === target' is true, so the function returns the index immediately without checking further elements.

What happens if the target is not in the array?

The loop runs through all elements without finding the target, then returns -1 after the loop ends, as shown by the exit_note explaining search stops only when target is found or array ends.

Why do we check 'i < arr.length' in the loop?

To avoid checking outside the array bounds, ensuring we only check valid elements. This is implied in the concept_flow where we move to next index until the end is reached.

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of 'i' when the target is found?

A 2

B 1

C 0

D 3

💡 Hint

Check the 'Index Checked' column in step 3 where the target is found.

At which step does the search stop because the target is found?

A Step 1

B Step 2

C Step 3

D Step 4

💡 Hint

Look at the 'Action' column where the function returns the index.

If the target was 10 (not in array), what would the final result be?

A Index 2

B -1

C Index 0

D Undefined

💡 Hint

Refer to the exit_note and key_moments about what happens when target is not found.

Concept Snapshot

Linear Search Algorithm:
- Start from first element
- Check each element one by one
- If element == target, return index
- If end reached without finding, return -1
- Simple but can be slow for large arrays

Full Transcript

Linear Search checks each element in the array from start to end. It compares each element with the target value. If it finds the target, it returns the index immediately. If it reaches the end without finding the target, it returns -1. This method is simple and works on any list but can be slow if the list is long because it may check every element.

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