Linear Search Algorithm in DSA Typescript - Execution Trace

Concept Flow - Linear Search Algorithm

Start at index 0

↓

Check if element at index == target?

No→Move to next index

↓

Index < array length?

No→Target not found

↓

Return index

Start from the first element, check each one until the target is found or the list ends.

Execution Sample

DSA Typescript

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

Searches the array from start to end to find the target value and returns its index or -1 if not found.

Execution Table

Step	Operation	Index Checked	Element at Index	Target	Match?	Action	Result
1	Check element	0	4	3	No	Move to next index	Continue searching
2	Check element	1	2	3	No	Move to next index	Continue searching
3	Check element	2	3	3	Yes	Return index	Found at index 2

💡 Target found at index 2, search stops.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	Final
i	0	1	2	2	2
arr[i]	4	2	3	3	3
target	3	3	3	3	3
result	undefined	undefined	undefined	2	2

Key Moments - 3 Insights

Why does the search stop immediately when a match is found?

Because the algorithm returns the index as soon as arr[i] === target is true, as shown in step 3 of the execution_table.

What happens if the target is not in the array?

The loop completes without finding a match, and the function returns -1, indicating the target is not found (not shown here but implied after last index).

Why do we check each element one by one instead of jumping around?

Linear search checks elements sequentially because it does not assume the array is sorted, so it must check every element until it finds the target or reaches the end.

Visual Quiz - 3 Questions

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

A 0

B 2

C 1

D 3

💡 Hint

Check the 'Index Checked' column in the row where 'Match?' is 'Yes'.

At which step does the algorithm decide to return the index?

A Step 3

B Step 2

C Step 1

D After the loop ends

💡 Hint

Look at the 'Action' column where it says 'Return index'.

If the target was 5 instead of 3, what would happen in the execution_table?

A The search would find the target at index 1.

B The search would stop at step 3 with a match.

C The search would continue until the end and return -1.

D The search would return index 0 immediately.

💡 Hint

Think about what happens when no element matches the target in the 'Match?' column.

Concept Snapshot

Linear Search Algorithm:
- Start at index 0
- Check each element sequentially
- If element == target, return index
- If end reached without match, return -1
- Works on unsorted arrays
- Simple but can be slow for large arrays

Full Transcript

Linear search starts at the first element of the array and checks each element one by one to see if it matches the target value. If a match is found, it returns the index immediately. If the search reaches the end without finding the target, it returns -1 to indicate the target is not present. This method works on any array, sorted or not, but can be slow if the array is large because it may need to check every element.