Golang search for an element in slice [SOLVED]


GO

Author: Tuan Nguyen
Reviewer: Deepak Prasad

In this tutorial, we will try to implement some algorithms to search for an element in a slice. Go before version 1.18 does not provide any built-in methods to perform the searching operations, so we can write our own function to implement some searching algorithms such as linear search or binary search.

 

Example 1: Return the index of the search element using the slices.IndexFunc() function

func IndexFunc[E any](s []E, f func(E) bool) int: IndexFunc returns the first index i satisfying f(s[i]), or -1 if none do.

Starting with Go 1.18 which adds generics support, we can use the slices.IndexFunc() function to return the index of the element we want to search. The example below shows how we can use this function in Golang:

package main

import (
	"fmt"

	"golang.org/x/exp/slices"
)

func main() {
	intslice := []int{1, 2, 2, 41, 1, 25, 5}
	searchElement := 1
	idx := slices.Index(intslice, searchElement)
	fmt.Printf("the index of %v is %v\n", searchElement, idx)

	strslice := []string{"this", "is", "the", "first", "example"}
	searchElement2 := "the"
	idx2 := slices.Index(strslice, searchElement2)
	fmt.Printf("the index of %v is %v", searchElement2, idx2)
}

Output:

the index of 1 is 0
the index of the is 2

 

Example 2: Return the index of the search element using the slices.BinarySearch() function

func BinarySearch[E constraints.Ordered](x []E, target E) (int, bool): BinarySearch searches for target in a sorted slice and returns the position where the target is found, or the position where target would appear in the sort order; it also returns a bool saying whether the target is really found in the slice. The slice must be sorted in increasing order.

If you do want to check if the element is in the slice or not, you can use the BinarySearch() function. Before using this function, make sure your slice is sorted. Here is an example of using the BinarySearch() to check if the element is in the slice or not:

package main

import (
	"fmt"

	"golang.org/x/exp/slices"
)

func main() {
	intslice := []int{1, 2, 3, 4, 5, 6, 7}
	searchElement := 4
	idx, _ := slices.BinarySearch(intslice, searchElement)
	fmt.Printf("the index of %v is %v\n", searchElement, idx)

	strslice := []string{"Anna", "Bob", "Daniel", "Fru", "Sean"}
	searchElement2 := "Daniel"
	idx2, _ := slices.BinarySearch(strslice, searchElement2)
	fmt.Printf("the index of %v is %v", searchElement2, idx2)
}

Output:

the index of 4 is 3
the index of Daniel is 2

 

Example 3: Using the sort.Search() function

The combination of sort.Slice() plus sort.Search() functions, we can easily search an element in a slice:

func Slice(x any, less func(i, j int) bool): Slice sorts the slice x given the provided less function. It panics if x is not a slice.

func Search(n int, f func(int) bool) int: return:

  • the smallest index i at which x <= a[i]
  • or len(a) if there is no such index.

Let's take a look at the example below to see how we can use the sort package to search for an element in a slice:

package main

import (
	"fmt"
	"sort"
)

func main() {
	strSlice := []string{"Daniel", "Anna", "Bengi", "Faker", "Bang"}

	// sort the slice ASC order
	sort.Slice(strSlice, func(i, j int) bool {
		return strSlice[i] <= strSlice[j]
	})

	searchElemnt1 := "Clair"
	// return the smallest element which >= the searching element
	idx1 := sort.Search(len(strSlice), func(i int) bool {
		return searchElemnt1 <= strSlice[i]
	})

	// return the smallest element which >= the searching element
	searchElemnt2 := "Anna"
	idx2 := sort.Search(len(strSlice), func(i int) bool {
		return searchElemnt2 <= strSlice[i]
	})

	// check if that smallest element equals to the searching element
	if idx1 < len(strSlice) && strSlice[idx1] == searchElemnt1 {
		fmt.Printf("Found %s at index %d in %v.\n", searchElemnt1, idx1, strSlice)
	} else {
		fmt.Printf("Not found %s in %v.\n", searchElemnt1, strSlice)
	}

	if idx2 < len(strSlice) && strSlice[idx2] == searchElemnt2 {
		fmt.Printf("Found %s at index %d in %v.\n", searchElemnt2, idx2, strSlice)
	} else {
		fmt.Printf("Not found %s in %v.\n", searchElemnt2, strSlice)
	}
}

Output:

Not found Clair in [Anna Bang Bengi Daniel Faker].
Found Anna at index 0 in [Anna Bang Bengi Daniel Faker].

 

Example 4: Implement the linear search algorithm

 Linear search or sequential search is a method for finding an element within a list. It sequentially checks each element of the list until a match is found or the whole list has been searched. The example below shows how we can use a simple loop to search for an element in a slice:

package main

import "fmt"

func main() {
	strSlice := []string{"this", "is", "a", "very", "simple", "example"}

	testStr1 := "this"
	testStr2 := "that"

	ind1 := FindIndex(strSlice, testStr1)
	ind2 := FindIndex(strSlice, testStr2)

	fmt.Println("Search \"this\" element in the slice. Is it in the slice? ", CheckContain(strSlice, testStr1), " index found:", ind1)
	fmt.Println("Search \"that\" element in the slice. Is it in the slice? ", CheckContain(strSlice, testStr2), " index found:", ind2)
}

// find the index of an element
func FindIndex(strSlice []string, element string) int {
	for ind, val := range strSlice {
		if val == element {
			return ind
		}
	}
	// if not found, return -1
	return -1
}

// Check if element is in slice or not
func CheckContain(strSlice []string, element string) bool {
	for _, val := range strSlice {
		if element == val {
			return true
		}
	}
	return false
}

Output:

Search "this" element in the slice. Is it in the slice?  true  index found: 0
Search "that" element in the slice. Is it in the slice?  false  index found: -1

 

Example 5: Implement the binary search algorithm

If we want to do the binary search, make sure the slice is sorted. This example below implement the binary search algorithm and apply it to find the index of the first found element:

package main

import "fmt"

func main() {
	strSlice := []string{"Anna", "Bang", "Bengi", "Daniel", "Faker"}
	fmt.Println(binarySearch("Bengi", strSlice))
	fmt.Println(binarySearch("BengBeng", strSlice))
}

// binary search for the index of element
func binarySearch(element string, strSlice []string) int {
	low := 0
	high := len(strSlice) - 1

	for low <= high {
		med := (low + high) / 2
		if strSlice[med] < element {
			low = med + 1
		} else {
			high = med - 1
		}
	}

	if low == len(strSlice) || strSlice[low] != element {
		return -1
	}

	return low
}

Output:

2
-1

 

Summary

In this tutorial, we have provided some examples of how we can search for an element in a slice. We can use the slices package with the IndexFunc() or BinarySearch() function or the sort.Sort and sort.Search to return the index of the element in the slice. We also can implement our linear search by using a simple loop or binary search. Noted that, to use a binary search algorithm, the slice to be operated on must have already been sorted.

 

References

https://pkg.go.dev/golang.org/x/exp/slices
https://en.wikipedia.org/wiki/Linear_search
How to search for an element in a golang slice - Stack Overflow

 

Views: 259
Tuan Nguyen

Tuan Nguyen

He is proficient in Golang, Python, Java, MongoDB, Selenium, Spring Boot, Kubernetes, Scrapy, API development, Docker, Data Scraping, PrimeFaces, Linux, Data Structures, and Data Mining. With expertise spanning these technologies, he develops robust solutions and implements efficient data processing and management strategies across various projects and platforms. You can connect with him on his LinkedIn profile.

Can't find what you're searching for? Let us assist you.

Enter your query below, and we'll provide instant results tailored to your needs.

If my articles on GoLinuxCloud has helped you, kindly consider buying me a coffee as a token of appreciation.

Buy GoLinuxCloud a Coffee

For any other feedbacks or questions you can send mail to admin@golinuxcloud.com

Thank You for your support!!

Leave a Comment