Golang DSA Chapter 8 Part 2: Searching, Recursion, and Hashing
Welcome back. In Part 1 we covered the sorting side of Chapter 8, from bubble sort all the way to quick sort. Now we’re picking up the second half: searching algorithms, recursion, and hashing. These are the tools you use when you already have your data and need to find stuff in it, or when you need to transform it for fast lookups.
Let’s get into it.
Searching: Finding Things in Collections
Search algorithms do exactly what the name says. You have a collection of data, you have a key, and you want to know if that key exists (and where). The book covers three flavors: linear, binary, and interpolation. Each one trades off simplicity for speed.
A few factors come into play when choosing which search algorithm to use: the type of input, whether the data is sorted, correctness requirements, and how efficient you need it to be. For small datasets, simple is fine. For large ones, you want something smarter.
Linear Search: The Brute Force Way
Linear search is the simplest approach. You start at the beginning and check every single element until you find what you’re looking for, or you run out of elements. That’s it.
The time complexity is O(n), which means in the worst case you check every element. Not great for large collections, but perfectly fine when your dataset is small or unsorted.
Here’s how it looks in Go:
package main
import (
"fmt"
)
func LinearSearch(elements []int, findElement int) bool {
var element int
for _, element = range elements {
if element == findElement {
return true
}
}
return false
}
func main() {
var elements []int
elements = []int{15, 48, 26, 18, 41, 86, 29, 51, 20}
fmt.Println(LinearSearch(elements, 48))
}
You pass in a slice and the element you want to find. The function loops through everything, and the moment it finds a match, it returns true. If it gets through the whole slice without finding anything, it returns false.
Simple, readable, works every time. Just not the fastest option when your data gets big.
Binary Search: Cut the Problem in Half
Binary search is way faster, but it comes with a requirement: your data must be sorted first. The idea is you look at the middle element of the collection. If your target is smaller, you throw away the right half. If it’s bigger, you throw away the left half. Then you repeat on what’s left.
This gives you a time complexity of O(log n), which is a huge improvement over linear search. Every step cuts your search space in half.
Go’s standard library actually has a built-in function for this in the sort package:
package main
import (
"fmt"
"sort"
)
func main() {
var elements []int
elements = []int{1, 3, 16, 10, 45, 31, 28, 36, 45, 75}
var element int
element = 36
var i int
i = sort.Search(len(elements), func(i int) bool { return elements[i] >= element })
if i < len(elements) && elements[i] == element {
fmt.Printf("found element %d at index %d in %v\n", element, i, elements)
} else {
fmt.Printf("element %d not found in %v\n", element, elements)
}
}
The sort.Search function takes the length of your slice and a comparison function. It returns the index where the element would be, and then you verify it’s actually there. The nice thing is you don’t have to write the binary search logic yourself.
One thing to keep in mind: if your slice isn’t sorted, sort.Search will give you garbage results. Always sort first.
Interpolation Search: Smarter Than Binary
Interpolation search takes the binary search idea and makes it smarter. Instead of always checking the middle, it estimates where the target element probably is, based on the values at the low and high ends of the search space. Think of it like looking up a name in a phone book. You wouldn’t start in the middle if the name starts with “A”, you’d start near the beginning.
The time complexity is O(log log n) in the best case, which is even better than binary search. But it only works well when data is uniformly distributed. If your data is clustered in weird ways, it can actually perform worse.
Here’s the Go implementation:
package main
import (
"fmt"
)
func InterpolationSearch(elements []int, element int) (bool, int) {
var mid int
var low int
low = 0
var high int
high = len(elements) - 1
for elements[low] < element && elements[high] > element {
mid = low + ((element-elements[low])*(high-low))/(elements[high]-elements[low])
if elements[mid] < element {
low = mid + 1
} else if elements[mid] > element {
high = mid - 1
} else {
return true, mid
}
}
if elements[low] == element {
return true, low
} else if elements[high] == element {
return true, high
} else {
return false, -1
}
}
func main() {
var elements []int
elements = []int{2, 3, 5, 7, 9}
var element int
element = 7
var found bool
var index int
found, index = InterpolationSearch(elements, element)
fmt.Println(found, "found at", index)
}
The key line is the mid calculation. Instead of (low + high) / 2 like binary search, it uses the actual values to estimate position. The formula is: low + ((element - elements[low]) * (high - low)) / (elements[high] - elements[low]). It’s basically doing proportional math to guess where the element should be.
The function returns both a boolean (found or not) and the index. If the element isn’t there, you get false and -1.
Recursion: Functions That Call Themselves
Recursion is when a function calls itself to solve a problem by breaking it down into smaller versions of the same problem. You need two things for it to work: a base case that stops the recursion, and a recursive step that moves toward that base case.
If you forget the base case, you get a stack overflow. The function keeps calling itself forever until Go runs out of memory. So always make sure there’s a way out.
The classic example is calculating a factorial. The factorial of 5 is 5 * 4 * 3 * 2 * 1. You can express that recursively: the factorial of n is n * factorial(n-1), and the factorial of 1 is just 1.
package main
import (
"fmt"
)
func Factor(num int) int {
if num <= 1 {
return 1
}
return num * Factor(num-1)
}
func main() {
var num int = 12
fmt.Println("Factorial: %d is %d", num, Factor(num))
}
The Factor function checks if num is 1 or less. If so, it returns 1 (that’s the base case). Otherwise, it multiplies num by the factorial of num-1. Each call gets closer to the base case, so it always terminates.
Recursion shows up everywhere in algorithms. We already saw it in quick sort and merge sort from Part 1. Binary search can also be implemented recursively, though the iterative version is usually preferred in Go because of the overhead of function calls.
The thing to watch out for with recursion in Go: there’s no tail-call optimization. Every recursive call adds a new frame to the call stack. For very deep recursion (thousands or millions of calls), you’ll want to convert to an iterative approach instead.
Hashing: Fast Lookups with Hash Functions
Hashing is about transforming data into a fixed-size value (a hash) that you can use for fast lookups and comparisons. Hash functions were introduced earlier in the book (Chapter 4), and here we see a practical implementation using Go’s crypto/sha1 package.
The idea: you feed bytes into a hash function, and you get back a fixed-length byte sequence. The same input always produces the same output, but different inputs (usually) produce different outputs.
Here’s a basic hash creation function:
package main
import (
"fmt"
"crypto/sha1"
"hash"
)
func CreateHash(byteStr []byte) []byte {
var hashVal hash.Hash
hashVal = sha1.New()
hashVal.Write(byteStr)
var bytes []byte
bytes = hashVal.Sum(nil)
return bytes
}
You create a new SHA-1 hash, write your data into it, and call Sum(nil) to get the final hash bytes. Pretty straightforward.
Hashing Multiple Values with XOR
The book also shows how to combine hashes of two different values using XOR. This is useful when you want a single hash that represents a combination of inputs:
func CreateHashMultiple(byteStr1 []byte, byteStr2 []byte) []byte {
return xor(CreateHash(byteStr1), CreateHash(byteStr2))
}
func xor(byteStr1 []byte, byteStr2 []byte) []byte {
var xorbytes []byte
xorbytes = make([]byte, len(byteStr1))
var i int
for i = 0; i < len(byteStr1); i++ {
xorbytes[i] = byteStr1[i] ^ byteStr2[i]
}
return xorbytes
}
func main() {
var bytes []byte
bytes = CreateHashMultiple([]byte("Check"), []byte("Hash"))
fmt.Printf("%x\n", bytes)
}
The xor function takes two byte slices of the same length and XORs them element by element. The CreateHashMultiple function hashes each input separately, then XORs the results together. This gives you a combined hash that depends on both inputs.
XOR is a nice choice here because it’s simple, fast, and reversible. If you know one of the original hashes and the combined result, you can recover the other one.
Wrapping Up
That covers the second half of Chapter 8. Here’s a quick summary of what we went through:
- Linear search is the simplest, O(n), works on any collection
- Binary search is O(log n) but requires sorted data
- Interpolation search is O(log log n) in the best case, needs sorted and uniformly distributed data
- Recursion is a technique where functions call themselves, useful for divide-and-conquer problems
- Hashing transforms data into fixed-size values for fast lookups, and you can combine hashes with XOR
The pattern across all of these: there’s always a tradeoff. Linear search is simple but slow. Binary search is fast but needs sorted data. Interpolation search is even faster but needs specific data distributions. Pick the right tool for your situation.
Next up, we move into graphs and network representation in Chapter 9. That’s where things start getting really interesting.