Algorithms and Data Structures in Go: A Practical Guide

Algorithms and Data Structures in Go: From Theory to Practice

Go (Golang) is a modern compiled language that combines the performance of C with the simplicity of Python. However, to write efficient code in Go, knowing the syntax is not enough. Understanding algorithms and data structures is the key to creating fast, scalable applications. In this article, we will cover three fundamental topics: binary search, hash tables, and sorting, with real code examples in Go.

1. Binary Search: Speed and Accuracy

Binary search is a classic algorithm for finding an element in a sorted array. Instead of linear scanning (O(n)), it halves the search space at each step, working in O(log n). In Go, this is especially relevant for working with large slices.

Implementation in Go:

package main

import "fmt"

// BinarySearch returns the index of the element if found, otherwise -1func BinarySearch(arr []int, target int) int {    left, right := 0, len(arr)-1

    for left <= right {        mid := left + (right-left)/2 // protection against overflow

        if arr[mid] == target {            return mid        } else if arr[mid] < target {            left = mid + 1        } else {            right = mid - 1        }    }    return -1}

func main() {    data := []int{2, 5, 8, 12, 16, 23, 38, 45, 56, 72}    target := 23    index := BinarySearch(data, target)    fmt.Printf("Index of element %d: %d", target, index) // Output: Index of element 23: 5}

Practical Tips:

• Always check that the array is sorted. In Go, you can use sort.Ints() from the sort package.
• The formula mid := left + (right-left)/2 prevents integer overflow for large arrays.
• For working with strings, use sort.SearchStrings() from the standard library.

2. Hash Tables: Fast Data Access

In Go, the built-in hash table is map. It provides element access in O(1) on average. But it is important to understand how it works under the hood to avoid pitfalls. The hash table uses a hash function to convert a key into an array index (bucket). Collisions are resolved using chaining (separate lists for each bucket).

Example of working with map:

package main

import "fmt"

func main() {    // Creating a map    scores := make(map[string]int)    scores["Anna"] = 95    scores["Boris"] = 87    scores["Victor"] = 92

    // Search with existence check    name := "Boris"    if score, exists := scores[name]; exists {        fmt.Printf("Score of %s: %d", name, score)    } else {        fmt.Printf("Student %s not found", name)    }

    // Deletion    delete(scores, "Anna")

    // Iteration (order is not guaranteed!)    for key, value := range scores {        fmt.Printf("%s: %d", key, value)    }}

Important Points:

• Map in Go is a reference type. When passed to a function, changes will affect the original.
• Do not use a nil map for writing — this will cause a panic. Always initialize with make().
• The iteration order over a map is non-deterministic. If order is needed, use a separate slice of keys.
• Only comparable types can be used as keys: numbers, strings, booleans, pointers, structs without slices/maps.

3. Sorting: From Bubble to Quick

Go offers a powerful sort package that implements quicksort and other algorithms. But for educational purposes and understanding, it is important to write sorting manually. Let's look at two implementations: bubble sort (O(n²)) for small data and quicksort (O(n log n)) for large