As part of the new Go release, several exciting changes have been introduced to the Go ecosystem. While we’ve explored some of these changes in other articles about the maps package and the cmp package, there’s much more to discover beyond these two packages.
In this article, we’ll focus on the first part of the slices package, specifically its new search functionality. Like many other updates and newly introduced packages, this one is also built upon the foundation of generics, which were introduced in Go 1.18.
BinarySearch and BinarySearchFunc #
Let’s start by exploring the first pair of functions designed for efficiently searching a target value within sorted slices. In this context, we’re referring to the well-known Binary Search algorithm, which is renowned as one of the most significant algorithms and is frequently used in coding interviews. Below, you’ll find the signatures of both of these functions:
BinarySearch function
func BinarySearch[S ~[]E, E cmp.Ordered](x S, target E) (int, bool)BinarySearchFunc function
func BinarySearchFunc[S ~[]E, E, T any](x S, target T, cmp func(E, T) int) (int, bool)Looking at the signatures of both functions, we can identify some small differences between them, and these differences
serve specific purposes. The first function, BinarySearch, expects two arguments. The first argument should be a slice
of sorted items, and it must adhere to the Ordered
constraint. When the items are ordered, the algorithm can efficiently compare them using the
Compare function from the cmp package.
On the other hand, the second function, BinarySearchFunc, is more versatile. It allows searching within slices where
the items don’t necessarily conform to the Ordered constraint. This flexibility is achieved by introducing a third
argument, the comparison function. This function is responsible for comparing items and determining their order. It
will be called by the BinarySearchFunc itself to make comparisons.
Both functions return two values. The first value is the index of the item within the slice, and the second is a boolean value indicating whether the item was found in the slice or not. Let’s explore some examples below:
BinarySearch examples
fmt.Println(slices.BinarySearch([]int{1, 3, 5, 6, 7}, 5))
// Output:
// 2 true
fmt.Println(slices.BinarySearch([]int{1, 3, 5, 6, 7}, 9))
// Output:
// 5 false
fmt.Println(slices.BinarySearch([]int{1, 3, 5, 6, 7}, -5))
// Output:
// 0 false
fmt.Println(slices.BinarySearch([]string{"1", "3", "5", "6", "7"}, "5"))
// Output:
// 2 true
fmt.Println(slices.BinarySearch([]string{"1", "3", "5", "6", "7", "8"}, "9"))
// Output:
// 6 false
fmt.Println(slices.BinarySearch([]string{"1", "3", "5", "6", "7"}, "4"))
// Output:
// 2 falseTake a close look at the results returned by the BinarySearch function, especially when the item doesn’t exist in the
slice. In our examples, we encountered four such cases where the function returned 0, 2, 5, and 6. When the
requested item isn’t present in the slice, the function indicates where it should be positioned if it were to be added
to the slice. Since the slice is sorted, it’s possible to determine the appropriate position for the item within the slice.
Here’s how it works:
- If the target item is less than all other items in the slice, it should be placed at index
0. - If the target item is greater than all other items, it should be positioned at the end of the slice, which falls outside the index range of the current slice.
- Otherwise, the function calculates the suitable position for the item within the slice.
Now, let’s explore the cases for the other function, BinarySearchFunc.
BinarySearchFunc examples
fmt.Println(slices.BinarySearchFunc([]int{1, 3, 5, 6, 7}, 5, cmp.Compare[int]))
// Output:
// 2 true
fmt.Println(slices.BinarySearchFunc([]int{1, 3, 5, 6, 7}, 9, cmp.Compare[int]))
// Output:
// 5 false
fmt.Println(slices.BinarySearchFunc([]int{1, 3, 5, 6, 7}, -5, cmp.Compare[int]))
// Output:
// 0 false
fmt.Println(slices.BinarySearchFunc([]string{"1", "3", "5", "6", "7"}, "5", cmp.Compare[string]))
// Output:
// 2 true
fmt.Println(slices.BinarySearchFunc([]string{"1", "3", "5", "6", "7", "8"}, "9", cmp.Compare[string]))
// Output:
// 6 false
fmt.Println(slices.BinarySearchFunc([]string{"1", "3", "5", "6", "7"}, "4", cmp.Compare[string]))
// Output:
// 2 falseHere, we have simple examples using BinarySearchFunc, where we employed the same test cases as with the BinarySearch
function. However, this time, we had to provide a comparison function as an argument. In this case, we utilized the
Compare function from Go’s
Standard Library.
But what’s the real purpose of BinarySearchFunc then? Let’s explore the example below to understand its significance.
BinarySearchFunc complex example
type Exam struct {
Content string
Mark int
}
fmt.Println(slices.BinarySearchFunc([]Exam{
{
Content: "First",
Mark: 1,
},
{
Content: "Second",
Mark: 1,
},
{
Content: "Third",
Mark: 2,
},
{
Content: "Fourth",
Mark: 3,
},
}, Exam{
Content: "Third",
Mark: 2,
}, func(exam1 Exam, exam2 Exam) int {
compare := cmp.Compare(exam1.Mark, exam2.Mark)
if compare == 0 {
return cmp.Compare(exam1.Content, exam2.Content)
}
return compare
}))
// Output:
// 2 trueIn this example, we can see the true significance of BinarySearchFunc. If we intend to search for an element in a slice
that doesn’t consist of items of type Ordered, as in this case with a simple struct Exam, then we should use this
method. We can define our own comparison function to adapt the provided binary search solution to handle our specific
situation.
Min and MinFunc #
Now, let’s discuss something that we can easily understand just from the function names. Yes, we are talking about the
functions Min and MinFunc. We have already discussed the built-in
min and max functions, and the functions
in the slices package heavily rely on them. But before we dive into further explanation, let’s take a look at their signatures:
Min functions
func Min[S ~[]E, E cmp.Ordered](x S) EMinFunc functions
func MinFunc[S ~[]E, E any](x S, cmp func(a, b E) int) EThe purpose of both new functions is to find the minimum value in the slice provided as an argument to the function. In
the case of the Min function, the slice must contain items of the Ordered type, while in the case of the MinFunc,
there is no such requirement, but we must provide a comparison function as a second argument.
Example of Min function
fmt.Println(slices.Min([]int{1, 3, 9, 2, -1, 5, 7}))
// Output:
// -1
fmt.Println(slices.Min([]string{"bac", "aaa", "a", "cccc"}))
// Output:
// a
fmt.Println(slices.Min([]float64{1, 1, 1}))
// Output:
// 1
fmt.Println(slices.Min([]int{}))
// Output:
// panic: slices.Min: empty listExample of MinFunc function
fmt.Println(slices.MinFunc([]int{1, 3, 9, 2, -1, 5, 7}, cmp.Compare[int]))
// Output:
// -1
fmt.Println(slices.MinFunc([]string{"bac", "aaa", "a", "cccc"}, cmp.Compare[string]))
// Output:
// a
fmt.Println(slices.MinFunc([]float64{1, 1, 1}, cmp.Compare[float64]))
// Output:
// 1
type Exam struct {
Content string
Mark int
}
fmt.Println(slices.MinFunc([]Exam{
{
Content: "First",
Mark: 1,
},
{
Content: "Second",
Mark: 1,
},
{
Content: "Third",
Mark: 2,
},
{
Content: "Fourth",
Mark: 3,
},
}, func(exam1 Exam, exam2 Exam) int {
compare := cmp.Compare(exam1.Mark, exam2.Mark)
if compare == 0 {
return cmp.Compare(exam1.Content, exam2.Content)
}
return compare
}))
// Output:
// {First 1}In the provided examples, we can see that both functions work as expected. Min works fine with all types that are of
the Ordered type, and for other types, we should use MinFunc. One important note for these two methods is that both
expect to receive a slice with at least one element as an argument. In case that doesn’t happen, both functions will
panic, so make sure to handle this use case in your code.
Max and MaxFunc #
I’ll keep this section as brief as possible since this new pair of functions is a continuation of the previous pair. So, let’s take a look at them:
Max functions
func Max[S ~[]E, E cmp.Ordered](x S) EMaxFunc functions
func MaxFunc[S ~[]E, E any](x S, cmp func(a, b E) int) EAnd followed immediately with some examples:
Example of Min function
fmt.Println(slices.Max([]int{1, 3, 9, 2, -1, 5, 7}))
// Output:
// 9
fmt.Println(slices.Max([]string{"bac", "aaa", "a", "cccc"}))
// Output:
// cccc
fmt.Println(slices.Max([]float64{1, 1, 1}))
// Output:
// 1
fmt.Println(slices.Max([]int{}))
// Output:
// panic: slices.Max: empty listExample of MinFunc function
fmt.Println(slices.MaxFunc([]int{1, 3, 9, 2, -1, 5, 7}, cmp.Compare[int]))
// Output:
// -9
fmt.Println(slices.MaxFunc([]string{"bac", "aaa", "a", "cccc"}, cmp.Compare[string]))
// Output:
// cccc
fmt.Println(slices.MaxFunc([]float64{1, 1, 1}, cmp.Compare[float64]))
// Output:
// 1
type Exam struct {
Content string
Mark int
}
fmt.Println(slices.MaxFunc([]Exam{
{
Content: "First",
Mark: 1,
},
{
Content: "Second",
Mark: 1,
},
{
Content: "Third",
Mark: 2,
},
{
Content: "Fourth",
Mark: 3,
},
}, func(exam1 Exam, exam2 Exam) int {
compare := cmp.Compare(exam1.Mark, exam2.Mark)
if compare == 0 {
return cmp.Compare(exam1.Content, exam2.Content)
}
return compare
}))
// Output:
// {Fourth 3}As in all previous examples, here too, the Max and MaxFunc combo follows the same approach. Both functions search
for the maximum value in the provided slice, which must have at least one item; otherwise, both functions will panic.
Similar to the previous example, MaxFunc provides support for searching for the maximum in slices whose elements are
not of the type Ordered, but you should also provide the comparison function as an argument.
IsSorted and IsSortedFunc #
Now, let’s discuss two slightly different functions: IsSorted and IsSortedFunc. Below, you can find their signatures:
IsSorted function
func IsSorted[S ~[]E, E cmp.Ordered](x S) boolIsSortedFunc function
func IsSortedFunc[S ~[]E, E any](x S, cmp func(a, b E) int) boolThese two new functions check if the slices provided as arguments are sorted in ascending order. The only difference between
them is that IsSorted, as in some previous examples, only works with slices of items that are of type Ordered, whereas
the function IsSortedFunc accepts items of any type, but it is necessary that we provide our own comparison function
as the second argument.
Examples with IsSorted function
fmt.Println(slices.IsSorted([]int{1, 2, 3, 5, 5, 7, 9}))
// Output:
// true
fmt.Println(slices.IsSorted([]int{1, 3, 9, 2, -1, 5, 7}))
// Output:
// false
fmt.Println(slices.IsSorted([]int{-1, 1, 2, 3, 5, 7, 9}))
// Output:
// true
fmt.Println(slices.IsSorted([]int{9, 7, 5, 3, 2, 1, -1}))
// Output:
// false
fmt.Println(slices.IsSorted([]int{}))
// Output:
// true
fmt.Println(slices.IsSorted([]int(nil)))
// Output:
// trueAs we can observe, the IsSorted function returns a straightforward boolean value, indicating whether a slice is sorted
in ascending order. It’s essential to handle empty slices as an edge case, where the function returns true. Therefore,
this scenario should be appropriately addressed in the implementation. Similarly, we can utilize the IsSortedFunc
function in a similar fashion:
Examples with IsSortedFunc function
fmt.Println(slices.IsSortedFunc([]int{1, 3, 9, 2, -1, 5, 7}, cmp.Compare[int]))
// Output:
// false
fmt.Println(slices.IsSortedFunc([]string{"1", "2", "3", "5", "7", "9"}, cmp.Compare[string]))
// Output:
// true
fmt.Println(slices.IsSortedFunc([]string{"9", "7", "5", "3", "2", "1"}, cmp.Compare[string]))
// Output:
// false
fmt.Println(slices.IsSortedFunc([]string{"9", "7", "5", "3", "2", "1"}, func(a, b string) int {
return -1 * cmp.Compare(a, b)
}))
// Output:
// true
type Exam struct {
Content string
Mark int
}
fmt.Println(slices.IsSortedFunc([]Exam{
{
Content: "First",
Mark: 1,
},
{
Content: "Second",
Mark: 1,
},
{
Content: "Third",
Mark: 2,
},
{
Content: "Fourth",
Mark: 3,
},
}, func(exam1 Exam, exam2 Exam) int {
compare := cmp.Compare(exam1.Mark, exam2.Mark)
if compare == 0 {
return cmp.Compare(exam1.Content, exam2.Content)
}
return compare
}))
// Output:
// trueJust like in all the previous examples involving functions that require custom comparison logic, there are no surprises
here. The IsSortedFunc function allows us to check if a slice is sorted, without any requirement for the items to be
of type Ordered. It’s worth noting that we can effortlessly check if a slice is sorted in descending order by providing
our custom comparison function, which returns opposite values compared to the Compare function.
Conclusion #
New version of Golang, 1.21, delivered many new updates, affecting standard library as well. In this article we checked
how some functions from slices packages work. Those new methods give us now possibility to easily check ordering of the
items of any slice that we want.
