Search operation in Go
development golang search genericsSearching for an item in a collection or container is a common operation in programming. In Go, there are a few different ways that this can be done. In this snippet, let us explore the ways in which an item, be it a number or string, can be searched in a slice.
Brute force
The easiest and straight forward approach to look for an item’s presence in a slice is to loop over the slice and compare each element in the slice with the item to be searched. Let us see how this function would like for a number.
func searchInt(haystack []int, needle int) bool {
for _, v := range haystack {
if needle == v {
return true
}
}
return false
}
Prior to Go 1.18, a separate function for each data type was required. But in Go version 1.18, generics has been introduced. Let us see how one can use generics in Go to write a generic search function that works for all data types.
package main
import "fmt"
func main() {
haystack := []int{1, 3, 5, 2, 4}
needle := 3
fmt.Printf("Is %d present in haystack? %t\n", needle, search(haystack, needle))
haystackString := []string{"1", "2", "4", "3", "5"}
needleString := "3"
fmt.Printf("Is \"%s\" present in haystack? %t\n", needleString, search(haystackString, needleString))
}
func search[T comparable](haystack []T, needle T) bool {
for _, v := range haystack {
if v == needle {
return true
}
}
return false
}
Output:
Is 3 present in haystack? true
Is "3" present in haystack? true
Using sort package
Go provides a search function in sort package, but note that it uses binary search. Therefore the slice containing numbers or strings must already be sorted to use the search function.
package main
import (
"fmt"
"sort"
)
func main() {
haystack := []int{1, 2, 3, 4, 5}
needle := 3
fmt.Printf("Is %d present in haystack? %t\n", needle, search(haystack, needle))
haystackString := []string{"1", "2", "3", "4", "5"}
needleString := "3"
fmt.Printf("Is \"%s\" present in haystack? %t\n", needleString, search(haystackString, needleString))
}
func search[T comparable](haystack []T, needle T) bool {
index := sort.Search(len(haystack), func(i int) bool { return haystack[i] == needle })
return index < len(haystack) && haystack[index] == needle
}
Output:
Is 3 present in haystack? true
Is "3" present in haystack? true
The sort package also provides separate search functions for different data types like SearchInts(), SearchFloat64s() and SearchStrings().
package main
import (
"fmt"
"sort"
)
func main() {
haystack := []int{1, 2, 3, 4, 5}
needle := 3
fmt.Printf("Is %d present in haystack? %t\n", needle, searchInts(haystack, needle))
haystackString := []string{"1", "2", "3", "4", "5"}
needleString := "3"
fmt.Printf("Is \"%s\" present in haystack? %t\n", needleString, searchStrings(haystackString, needleString))
}
func searchInts(haystack []int, needle int) bool {
index := sort.SearchInts(haystack, needle)
return index < len(haystack) && haystack[index] == needle
}
func searchStrings(haystack []string, needle string) bool {
index := sort.SearchStrings(haystack, needle)
return index < len(haystack) && haystack[index] == needle
}
Outputs:
Is 3 present in haystack? true
Is "3" present in haystack? true
Experimental package
Go provides a package golang.org/x/exp/slices with experimental functions to operate on slices. This package provides Contains function to check if an item is present in the slice.
package main
import (
"fmt"
"golang.org/x/exp/slices"
)
func main() {
haystack := []int{1, 2, 3, 4, 5}
needle := 3
fmt.Printf("Is %d present in haystack? %t\n", needle, slices.Contains(haystack, needle))
haystackString := []string{"1", "2", "3", "4", "5"}
needleString := "3"
fmt.Printf("Is \"%s\" present in haystack? %t\n", needleString, slices.Contains(haystackString, needleString))
}
Output:
Is 3 present in haystack? true
Is "3" present in haystack? true
Note that this package also provides BinarySearch function, but the slice must already be sorted to use this function. You can find more details about this function at golang.org/x/exp/slices.
Related Posts
Ordered Printing With Goroutines In GoMultipart Requests in Go
Background Tasks in Go
Checksum Validation In Go
Search operation in Go