Go Program for Linear Search with Example and Explanation

A Go program for linear search uses a loop to check each element in a slice until it finds the target value, like for i, v := range arr { if v == target { return i }}.

Examples

Inputarr = []int{1, 2, 3, 4, 5}, target = 3

OutputElement found at index 2

Inputarr = []int{10, 20, 30, 40}, target = 25

OutputElement not found

Inputarr = []int{}, target = 1

OutputElement not found

How to Think About It

To do a linear search, start from the first item in the list and check if it matches the target. If it does, return the position. If not, move to the next item and repeat until you find the target or reach the end of the list.

Algorithm

1

Get the list of numbers and the target number to find.

2

Start from the first element in the list.

3

Compare the current element with the target.

4

If they match, return the current index.

5

If not, move to the next element and repeat.

6

If the end of the list is reached without a match, return -1.

Code

go

package main

import "fmt"

func linearSearch(arr []int, target int) int {
    for i, v := range arr {
        if v == target {
            return i
        }
    }
    return -1
}

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

Output

Element found at index 2

Dry Run

Let's trace searching for 7 in the list [5, 3, 7, 1, 9] through the code

1

Start loop

Check element at index 0: value 5, target 7

2

Compare values

5 != 7, continue to next index

3

Next element

Check element at index 1: value 3, target 7

4

Compare values

3 != 7, continue to next index

5

Next element

Check element at index 2: value 7, target 7

6

Match found

7 == 7, return index 2

Index	Value	Target	Match?
0	5	7	No
1	3	7	No
2	7	7	Yes

Why This Works

Step 1: Loop through elements

The for loop goes through each element in the slice one by one.

Step 2: Compare each element

Inside the loop, the code checks if the current element equals the target using if v == target.

Step 3: Return index if found

If a match is found, the function returns the current index immediately, stopping the search.

Step 4: Return -1 if not found

If the loop finishes without finding the target, the function returns -1 to indicate the target is not in the list.

Alternative Approaches

Using a while-like loop with index

go

package main

import "fmt"

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

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

This uses a manual index and a for loop like a while loop, which some may find clearer for beginners.

Using recursion

go

package main

import "fmt"

func linearSearch(arr []int, target, index int) int {
    if index >= len(arr) {
        return -1
    }
    if arr[index] == target {
        return index
    }
    return linearSearch(arr, target, index+1)
}

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

This recursive approach is elegant but uses more memory and can be harder to understand for beginners.

Complexity: O(n) time, O(1) space

Time Complexity

The search checks each element once, so time grows linearly with the list size.

Space Complexity

Only a few variables are used, so space stays constant regardless of input size.

Which Approach is Fastest?

The iterative for range loop is fastest and simplest; recursion adds overhead without speed benefits.

Approach	Time	Space	Best For
For range loop	O(n)	O(1)	Simple and readable code
Manual index loop	O(n)	O(1)	Beginners familiar with while loops
Recursion	O(n)	O(n)	Elegant but uses more memory