Linear search in Go

Key takeaways:
Linear search is a simple algorithm used to find an element in an unordered list by checking each element one by one until a match is found or the list ends.
Implementing linear search in Go is straightforward. The code involves iterating over a slice and comparing each element to the target value until a match is found.
The time complexity of linear search is $O(n)$ , where $n$ is the number of elements in the list.
The space complexity of linear search is $O(1)$ .

What is linear search?

Linear search, also known as sequential search, is a simple algorithm used to find a specific element in an unordered list. It works by checking each element in the list one by one until the target element is found or the entire list has been searched. Due to its straightforward approach, linear search is easy to implement but can be inefficient for large datasets, as it has a time complexity of $O(n)$ .

How linear search works: A step-by-step example

The concept behind linear search is simple: it checks each element in a list one by one until it finds the target element or reaches the end of the list. Let's walk through an example to illustrate how this works.

Consider the list of 7 elements: [2, 67, 12, 10, 23, 4, 9]. If we want to find the index of the number 4 in this list, linear search will start by comparing the first element (2) with the target (4). Since they don’t match, it moves to the next element (67) and repeats the process.

The search continues, comparing 12, 10, 23, and then 4. When it finds 4, the algorithm stops and returns the index where 4 is located—in this case, index 4.

If the target element was not in the list, linear search would continue checking all elements until it has iterated through the entire list.

This is illustrated below:

package main
import "fmt"
// linearSearch performs a search for the target element in the given array.
// It returns the index of the element if found, or -1 if not found.
func linearSearch(arr []int, target int) int {
    // Loop through the array using range to check each element
    for i, num := range arr {
        if num == target {
            return i // Return the index if the target element is found
        }
    }
    return -1 // Return -1 if the target element is not found in the array
}
func main() {
    // Example array and target value
    arr := []int{2, 67, 12, 10, 23, 4, 9}
    target := 4
    // Perform the search and get the index of the target element
    index := linearSearch(arr, target)
    // Output result based on whether the element was found or not
    if index != -1 {
        fmt.Printf("Element %d found at index %d\n", target, index)
    } else {
        fmt.Printf("Element %d not found in the list\n", target)
    }
}

Step-by-step code explanation

Line 1: We declare the main package. In Go, the main package is used to define the entry point for executable programs.
Line 3: The fmt package is imported to allow formatted input and output operations. In this program, it's used to print messages to the console (such as the result of the search).
Line 7: We declare the function linearSearch :
- It takes two arguments: a slice (array) of integers, arr, to search through, and the integer value target we're searching for in the array.
- The function returns an int, which is the index of the target element if found, or -1 if the element is not in the array.
Line 9: The for loop iterates through each element in the array using range. The range keyword returns two values: the index i and the value of the element num at that index.
Lines 10–21: If num matches the target, the function immediately returns the index i where the target was found.
Line 14: If no match is found after iterating through the entire array, the function returns -1 to indicate the element is not present.
Lines 17–31: The main function is defined to call the linearSearch function and display the results.

If you're looking to deepen your understanding of Go, we recommend exploring the resources like An Introduction to Programming in Go and Golang for Programmers, which provide comprehensive insights into the language and its features.

Time complexity of linear search algorithm

The time complexity of the linear search algorithm is $O(n)$ , where $n$ is the number of elements in the list. In the worst case, the algorithm may need to check every element in the list before finding the target or determining that the element is not present. Therefore, the time taken grows linearly with the size of the list.

Space complexity of linear search algorithm

The space complexity of linear search is $O(1)$ , meaning it requires a constant amount of extra space regardless of the size of the input list. Since linear search only needs to store a few variables (such as the current index or target element), its space requirements are minimal.

Frequently asked questions

Haven’t found what you were looking for? Contact Us

What is another name for the linear search algorithm?

Linear search, also known as the sequential search algorithm, is one of the simplest search techniques. It is primarily used to locate an element within an unordered list by examining each element one by one.

What search algorithm is more efficient than linear search?

Binary search is generally more efficient than linear search, especially for large datasets. While linear search has a time complexity of O(n), binary search operates with a time complexity of O(log n), making it faster for searching in sorted data. However, binary search requires the dataset to be sorted, whereas linear search can be used on unsorted data.

What is the fastest search algorithm?

The binary search algorithm is widely considered the fastest search method. It operates on sorted arrays and efficiently locates a specific value by repeatedly dividing the search space in half. Based on the “divide and conquer” principle, binary search is faster than linear search, making it ideal for large datasets.

What are the disadvantages of linear search?

Linear search has several limitations, including:

Inefficiency with large datasets: Its time complexity is O(n), which makes it slow, especially when the element is near the end of the list or absent entirely.
No advantage with sorted data: Unlike more advanced algorithms, linear search doesn’t take advantage of sorted data, often leading to unnecessary comparisons.
Sequential checking: The algorithm checks each element one by one, making it slower compared to more efficient search methods like binary search.

What is a real-life example of a linear search?

A common real-life example of linear search is searching through a stack of papers on your desk. To find a specific document, you would start by picking up the first paper and check if it’s the one you’re looking for. If not, you move on to the next paper, repeating the process until you find the right document or exhaust the stack.

Free Resources