How to search a string through a slice as efficiently as possible?

foo := []string{"foo","bar","FoO","baR"}
sayIfExists("baR") //func(string)bool

Can anyone make the sayIfExists() function with the highest efficiency?

for _,v := range foo {
    if givenStr == v {
       return true

this example is not efficient.because if I search the last value, it need to loop through the whole slice.

And it’s too bad for a very large dataset.

Any better idea?

If the slice has no order, then you are stuck with linear search, which is O(n). If it is sorted, you can do it in O(log(n)) with a binary search. That’s assuming you have no decision over the data structure and how it gets populated.

1 Like

use sort package

package main

import sort

func main() {
    foo := []string{"foo","bar","FoO","baR"}
    query := "baR"
    match := sort.SearchStrings(foo, "baR")
    if foo[match] < len(foo) && foo[match] == query {
         // match
    } else {
        // not match

the best way, use map, go map implement by hash table, it have O(1) time complexity

foo = map[string]struct{}{"foo":struct{}{}, "bar":struct{}{}, "FoO": struct{}{}, "baR": struct{}{}}

_, ok:= foo["baR"]
// process

But the hash has to be calculated. Most efficient version, especially if the set is dynamic, a prefix tree might be the most efficient thing, runtime at least.

It’s runtime depends on the length of the word to search. It’s memory overhead might be more than gos native maps though…


yes, prefix tree is better than hash when data is dynamic

Go maps are not O(1).

Yes this is the awesome solution but here comes the tradeoff
CPU vs memory.