Linear Search Algorithm in DSA Go - Execution Trace

Concept Flow - Linear Search Algorithm

Start at first element

↓

Check if element == target?

No→Move to next element

↓

More elements?

No→Target not found

↓

Return index

Start from the first element, check each one against the target. If found, return index; else move to next until end.

Execution Sample

DSA Go

arr := []int{4, 2, 7, 1, 3}
key := 1
for i, v := range arr {
    if v == key {
        return i
    }
}
return -1

Search for key 1 in array by checking each element one by one.

Execution Table

Step	Operation	Current Index	Current Value	Check (value == key?)	Action	Visual State
1	Start search	-	-	-	Start at index 0	[4] -> [2] -> [7] -> [1] -> [3]
2	Compare	0	4	4 == 1? No	Move to next index	[4] -> [2] -> [7] -> [1] -> [3]
3	Compare	1	2	2 == 1? No	Move to next index	[4] -> [2] -> [7] -> [1] -> [3]
4	Compare	2	7	7 == 1? No	Move to next index	[4] -> [2] -> [7] -> [1] -> [3]
5	Compare	3	1	1 == 1? Yes	Return index 3	[4] -> [2] -> [7] -> [1] -> [3]
6	End	-	-	-	Search ends, index 3 returned	[4] -> [2] -> [7] -> [1] -> [3]

💡 Target found at index 3, search stops.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	Final
i (index)	-	0	1	2	3	3
v (value)	-	4	2	7	1	1
key	1	1	1	1	1	1
foundIndex	N/A	N/A	N/A	N/A	3	3

Key Moments - 3 Insights

Why does the search stop immediately when the value matches the key?

Because linear search returns the index as soon as it finds the target, as shown in step 5 of the execution_table.

What happens if the target is not in the array?

The search checks all elements and then returns -1 after the last step, which is not shown here but would be after step 6.

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

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

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of 'v' at step 4?

A 1

B 7

C 2

D 4

💡 Hint

Check the 'Current Value' column at step 4 in the execution_table.

At which step does the search find the target value?

A Step 5

B Step 3

C Step 2

D Step 6

💡 Hint

Look for the step where 'Check (value == key?)' is 'Yes' in the execution_table.

If the key was 10 (not in array), what would happen to the 'Action' column in the last step?

A Return index of last element

B Stop at first element

C Return -1 indicating not found

D Return index 0

💡 Hint

Recall linear search returns -1 if target is not found after checking all elements.

Concept Snapshot

Linear Search Algorithm:
- Start at first element
- Check each element one by one
- 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 compares each element to the target value. If a match is found, it immediately returns the index of that element. If no match is found after checking all elements, 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 checks every element one by one.