Binary-Search

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 false Take 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.