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.

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, starting from the first, until it finds the target or reaches the end.

2. Step 2: Compare with other search methods

   Other methods like binary search divide the list or use extra data structures, but linear search is simple and direct.

3. Final Answer:

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

4. Quick Check:

   Linear search = check elements one by one [OK]

Hint: Linear search checks elements in order until found [OK]

Common Mistakes:

• Confusing linear search with binary search
• Thinking linear search requires sorted list
• Assuming linear search is faster than binary search always

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

easy

A. while i < len(arr) {

B. for i in arr {

C. foreach i in arr {

D. for i := 0; i < len(arr); i++ {

Solution

1. Step 1: Identify Go loop syntax for arrays

   In Go, the standard for loop to iterate over an array uses: for i := 0; i < len(arr); i++ { ... }

2. Step 2: Check other options for Go correctness

   Options B and C use syntax from other languages, and D is correct Go syntax.

3. Final Answer:

   for i := 0; i < len(arr); i++ { -> Option D

4. Quick Check:

   Go for loop syntax = for i := 0; i < len(arr); i++ { [OK]

Hint: Use Go's for loop with index and length [OK]

Common Mistakes:

• Using Python or JavaScript loop syntax in Go
• Forgetting to initialize loop variable
• Using while loop which is not common in Go

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

package main
import "fmt"
func main() {
  arr := []int{4, 2, 7, 1, 9}
  target := 7
  index := -1
  for i := 0; i < len(arr); i++ {
    if arr[i] == target {
      index = i
      break
    }
  }
  fmt.Println(index)
}

medium

A. 3

B. -1

C. 2

D. 7

Solution

1. Step 1: Trace the loop to find target 7 in array

   Array is [4, 2, 7, 1, 9]. Loop checks elements: index 0=4, 1=2, 2=7 matches target.

2. Step 2: Assign index and break loop

   When arr[2] == 7, index is set to 2 and loop breaks, so index remains 2.

3. Final Answer:

   2 -> Option C

4. Quick Check:

   Target 7 found at index 2 [OK]

Hint: Stop loop when target found, print index [OK]

Common Mistakes:

• Returning element value instead of index
• Not breaking loop and returning last index
• Confusing index with value

4. Find the error in this Go linear search code snippet:

arr := []int{3, 5, 8, 6}
target := 6
index := -1
for i := 0; i <= len(arr); i++ {
  if arr[i] == target {
    index = i
    break
  }
}
fmt.Println(index)

medium

A. The target value should be declared as a pointer

B. Loop condition should be i < len(arr), not i <= len(arr)

C. Variable 'index' should be initialized to 0 instead of -1

D. The array should be sorted before searching

Solution

1. Step 1: Check loop boundary condition

   The loop uses i <= len(arr), but valid indices are 0 to len(arr)-1. Using <= causes out-of-range error.

2. Step 2: Correct loop condition

   Change loop to i < len(arr) to avoid accessing invalid index.

3. Final Answer:

   Loop condition should be i < len(arr), not i <= len(arr) -> Option B

4. Quick Check:

   Loop index must be less than length [OK]

Hint: Use i < len(arr) to avoid index out of range [OK]

Common Mistakes:

• Using <= instead of < in loop condition
• Initializing index incorrectly
• Thinking array must be sorted for linear search

5. You have a list of student names: ["Anna", "Bob", "Clara", "David", "Eva"]. You want to find the position of "David" using linear search in Go. Which code snippet correctly implements this and prints the index or -1 if not found?

hard

A. names := []string{"Anna", "Bob", "Clara", "David", "Eva"}
target := "David"
index := -1
for i := 0; i < len(names); i++ {
if names[i] == target {
index = i
break
}
}
fmt.Println(index)

B. names := []string{"Anna", "Bob", "Clara", "David", "Eva"}
target := "David"
index := 0
for i := 1; i <= len(names); i++ {
if names[i] == target {
index = i
break
}
}
fmt.Println(index)

C. names := []string{"Anna", "Bob", "Clara", "David", "Eva"}
target := "David"
index := -1
for i := 0; i < len(names); i++ {
if names[i] != target {
index = i
break
}
}
fmt.Println(index)

D. names := []string{"Anna", "Bob", "Clara", "David", "Eva"}
target := "David"
index := -1
for i := 0; i < len(names); i++ {
if names[i] == target {
index = i + 1
break
}
}
fmt.Println(index)

Solution

1. Step 1: Check loop and index initialization

   names := []string{"Anna", "Bob", "Clara", "David", "Eva"} target := "David" index := -1 for i := 0; i < len(names); i++ { if names[i] == target { index = i break } } fmt.Println(index) initializes index to -1 and loops from 0 to len(names)-1 correctly.

2. Step 2: Verify condition and output

   It compares names[i] == target and breaks on match, printing correct zero-based index or -1 if not found.

3. Final Answer:

   Option A code correctly implements linear search and prints index or -1 -> Option A

4. Quick Check:

   Linear search with correct loop and condition [OK]

Hint: Loop from 0 to len-1, compare equal, break and print index [OK]

Common Mistakes:

• Using wrong loop bounds causing runtime error
• Setting index incorrectly on no match
• Adding 1 to index causing off-by-one error