Series
Here are all the posts in this series about the slices package.
Introduction
Go’s most important data structure is the slice and it was designed from the beginning to be mechanically sympathetic with the hardware. To learn more about that, check out Bill Kennedy’s Ultimate Go video. Thanks to the introduction of generics in Go 1.18, the language team has been experimenting with a new package called slices. This package provides an API that provides various functions that are useful when working with slices.
https://pkg.go.dev/golang.org/x/exp/slices
One very cool thing about this experimental package is that it’s planned to be part of the standard library in an upcoming minor release of Go. In this series, I will introduce the API of the slices package and in this post, I will explore the Binary Search APIs.
Binary Search
Binary search is a search algorithm that finds an element within a sorted list. It works by looking at the element in the middle of the list for a match and if not found, cuts the list in half and repeats. For example, given the list of numbers: [1, 2, 3, 4, 5], the search would compare the target value with the number 3, and then divide that list in half and try again.
You can see a live example of this on the Ultimate Go Tour.
https://tour.ardanlabs.com/tour/algorithms-searches/1
A binary search on average has a time complexity O(log N) and in layman’s terms that means the number of operations performed will grow in a logarithmic curve as N (the number of elements within the array) grows.
Figure 1
Courtesy of What is Logarithmic Time Complexity? A Complete Tutorial
API Example
The code that will be reviewed in this post lives here.
https://github.com/ardanlabs/gotraining/blob/master/topics/go/packages/slices/example1/example1.go
There are two versions of the binary search API, one that takes a slice and the target value, and one that takes the same arguments plus a custom compare function. I will start with the first version of the API.
Listing 1
01 package main
02
02 import (
04 "fmt"
05
06 "golang.org/x/exp/slices"
07 )
08
09 func main() {
10 list := []int{1, 2, 3, 4, 5, 6}
11 fmt.Println("Slice", list)
. . .
30 }
In listing 1 on line 06, you can see the import for the experimental slices package. Then on line 09-11, you see a slice of integers pre-sorted and the display of that list.
Listing 2
16 index, found := slices.BinarySearch(list, 9)
17 fmt.Printf("Looking for 9, idx[%d], found[%v]\n", index, found)
18
19 index, found = slices.BinarySearch(list, 5)
20 fmt.Printf("Looking for 5, idx[%d], found[%v]\n", index, found)
In listing 2 on lines 13 and 16, you see the calls to the BinarySearch API from the slices package. In the first call I am looking for a value that does not exist and in the second I am looking for the 5th item in the list. The API returns a boolean that specifies if the value was found or not, and the index position where the value was found. If the value is not found, an index position of where the value would have been is returned.
Listing 3
$ go run example1.go
Slice [1 2 3 4 5 6]
Looking for 9, idx[6], found[false]
Looking for 5, idx[4], found[true]
Listing 3 shows the output of running the current version of the program. As expected, the BinarySearch API could not find the number 9 in the list, and reported it would have been at index 6 if found. It did however find the number 5 at index 4.
If you want more control over how the algorithm works, or you are working with a custom type and need to control what it means for two values to be equal, there is a BinarySearchFunc API.
Listing 4
32 // Compare needs to return 0 if the two values are the same, a positive
33 // number of a > b, and a negative number of a < b.
34 func compare(a int, b int) int {
35 return a - b
36 }
Listing 4 shows a custom compare function that accepts two values of the list’s type and requires the function to return an integer. Returning zero means the two values are equal, returning a positive number means value a is greater than value b, and returning a negative number means the opposite. In this case, the compare function is comparing integers so using subtraction satisfies the rules.
Listing 5
25 index, found = slices.BinarySearchFunc(list, 7, compare)
26 fmt.Printf("Looking for 7, idx[%d], found[%v]\n", index, found)
27
28 index, found = slices.BinarySearchFunc(list, 2, compare)
29 fmt.Printf("Looking for 2, idx[%d], found[%v]\n", index, found)
Listing 5 shows the calls to the BinarySearchFunc API where the compare function is provided.
Listing 6
$ go run example1.go
Slice [1 2 3 4 5 6]
Looking for 7, idx[6], found[false]
Looking for 2, idx[1], found[true]
Listing 6 shows the output from calling the BinarySeachFunc API. Though these calls are using a different target, the behavior is the same.
Conclusion
You can see how cool this new slices package is by providing the BinarySearch API. In the next post, we will explore the Clip, Clone, and Compact APIs.
If you want to cheat and see all the examples I have prepared for future posts, check out the Go training repo.
https://github.com/ardanlabs/gotraining/tree/master/topics/go/packages/slices