Find element in slice/array with linear or binary search
source link: https://yourbasic.org/golang/find-search-contains-slice/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Find element in slice/array with linear or binary search
Linear search
Go doesn’t have an out-of-the-box linear search function for slices and arrays. Here are two example linear search implementations, which you can use as templates.
// Find returns the smallest index i at which x == a[i],
// or len(a) if there is no such index.
func Find(a []string, x string) int {
for i, n := range a {
if x == n {
return i
}
}
return len(a)
}
// Contains tells whether a contains x.
func Contains(a []string, x string) bool {
for _, n := range a {
if x == n {
return true
}
}
return false
}
Binary search
If the array is sorted, you can use a binary search instead. This will be much more efficient, since binary search runs in worst-case logarithmic time, making O(log n) comparisons, where n is the size of the slice.
There are the three custom binary search functions:
sort.SearchInts
,
sort.SearchStrings
or
sort.SearchFloat64s
.
They all have the signature
func SearchType(a []Type, x Type) int
and return
- the smallest index
i
at whichx <= a[i]
- or
len(a)
if there is no such index.
The slice must be sorted in ascending order.
a := []string{"A", "C", "C"}
fmt.Println(sort.SearchStrings(a, "A")) // 0
fmt.Println(sort.SearchStrings(a, "B")) // 1
fmt.Println(sort.SearchStrings(a, "C")) // 1
fmt.Println(sort.SearchStrings(a, "D")) // 3
Generic binary search
There is also a generic binary search function sort.Search
.
func Search(n int, f func(int) bool) int
It returns
- the smallest index
i
at whichf(i)
is true, - or
n
if there is no such index.
It requires that f
is false for some (possibly empty) prefix
of the input range and then true for the remainder.
This example mirrors the one above, but uses the generic sort.Search
instead of sort.SearchInts
.
a := []string{"A", "C", "C"}
x := "C"
i := sort.Search(len(a), func(i int) bool { return x <= a[i] })
if i < len(a) && a[i] == x {
fmt.Printf("Found %s at index %d in %v.\n", x, i, a)
} else {
fmt.Printf("Did not find %s in %v.\n", x, a)
}
// Output: Found C at index 1 in [A C C].
Further reading
The map option
If you are doing repeated searches and updates, you may want to use a map instead of a slice. A map provides lookup, insert, and delete operations in O(1) expected amortized time.
Further reading
Share:
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK