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.