Linear Search Algorithm in DSA Go

Mental Model

Look at each item one by one until you find the one you want or reach the end.

Analogy: Like looking through a row of books on a shelf one by one to find your favorite book.

Array: [3] -> [7] -> [1] -> [9] -> [5] -> null
Index:  0      1      2      3      4
Search for: 9
                  ↑

Dry Run Walkthrough

Input: array: [3, 7, 1, 9, 5], search value: 9

Goal: Find the index of value 9 in the array or say it is not found

Step 1: Check element at index 0

[3] -> [7] -> [1] -> [9] -> [5]
 ↑

Why: Start from the first element to see if it matches the search value

Step 2: Check element at index 1

[3] -> [7] -> [1] -> [9] -> [5]
      ↑

Why: First element was not 9, move to next element

Step 3: Check element at index 2

[3] -> [7] -> [1] -> [9] -> [5]
            ↑

Why: Keep checking each element until we find 9 or reach the end

Step 4: Check element at index 3

[3] -> [7] -> [1] -> [9] -> [5]
                  ↑

Why: Found the element 9 at index 3, stop searching

Result:

Final array: [3] -> [7] -> [1] -> [9] -> [5]
Index found: 3

Annotated Code

DSA Go

package main

import "fmt"

func linearSearch(arr []int, target int) int {
    for i, val := range arr {
        if val == target {
            return i // found target, return index
        }
    }
    return -1 // target not found
}

func main() {
    arr := []int{3, 7, 1, 9, 5}
    target := 9
    index := linearSearch(arr, target)
    if index != -1 {
        fmt.Printf("Index found: %d\n", index)
    } else {
        fmt.Println("Value not found")
    }
}

for i, val := range arr {

iterate over each element to check for target

if val == target {

compare current element with target value

return i // found target, return index

stop search and return index when target found

return -1 // target not found

return -1 if target is not in array

Output

Index found: 3

Complexity Analysis

Time: O(n) because in the worst case we check every element once

Space: O(1) because we only use a few variables regardless of input size

vs Alternative: Compared to binary search which is O(log n), linear search is slower but works on unsorted data

Edge Cases

empty array

returns -1 immediately because there are no elements to check

DSA Go

for i, val := range arr {

target is first element

returns index 0 immediately without checking other elements

DSA Go

if val == target {

target not in array

checks all elements and returns -1 at the end

DSA Go

return -1 // target not found

When to Use This Pattern

When you need to find an item in a list without any order, use linear search because it checks each item one by one.

Common Mistakes

Mistake: Stopping the search too early without checking all elements
Fix: Only stop when the target is found or after checking every element

Mistake: Returning the value instead of the index
Fix: Return the index where the target is found, not the value itself

Summary

It looks through each item in a list one by one to find a target value.

Use it when the list is unsorted or small and you need a simple search.

The key is to check every element until you find the target or reach the end.

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