Linear Search Algorithm in DSA C++ - Execution Trace

Concept Flow - Linear Search Algorithm

Start at index 0

↓

Check if element at index == target?

No→Move to next index

↓

Index < array size?

No→Target not found

↓

Return index

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

Execution Sample

DSA C++

int linearSearch(int arr[], int size, int target) {
  for (int i = 0; i < size; i++) {
    if (arr[i] == target) return i;
  }
  return -1;
}

Searches for target in array by checking each element from start to end.

Execution Table

Step	Operation	Index (i)	Element Checked	Condition (arr[i] == target)	Action	Result/Return
1	Check element	0	4	4 == 3? False	Move to next index
2	Check element	1	2	2 == 3? False	Move to next index
3	Check element	2	3	3 == 3? True	Return index 2	2
4	Exit	-	-	-	-	Search ends with index 2

💡 Target found at index 2, so 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
Condition (arr[i] == target)	False	False	True	True	True
Return value	None	None	None	2	2

Key Moments - 3 Insights

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

Because the condition arr[i] == target becomes True at step 3, the function returns the index immediately, stopping further checks as shown in execution_table row 3.

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, indicating target not found. This is shown by the exit_note and would be a row after all elements checked.

Why do we check condition before moving to the next index?

We must check if the current element matches the target before moving on, to avoid missing the target. The execution_table shows condition checked first, then action decided.

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 (i)' column in step 3 where condition is True.

At which step does the condition arr[i] == target become True?

A Step 1

B Step 2

C Step 3

D Step 4

💡 Hint

Look at the 'Condition (arr[i] == target)' column in the execution_table.

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

A The search would return -1 after checking all elements

B The search would stop at step 1

C The search would return index 2

D The search would return index 0

💡 Hint

Think about what happens when no element matches the target in the loop.

Concept Snapshot

Linear Search Algorithm:
- Start from index 0
- Check each element if it equals target
- If yes, return index immediately
- If no, move to next element
- If end reached without match, return -1

Full Transcript

Linear Search Algorithm checks each element in an array one by one from the start. It compares the current element with the target. If they match, it returns the current index immediately, stopping the search. If no element matches by the end, it returns -1 indicating target not found. This simple method is easy to understand and works on unsorted arrays.