Сложность поиска в слайсе vs map?

Поиск в слайсе — O(n), линейный перебор всех элементов. Поиск в map — O(1) амортизированный, благодаря хеш-таблице.

// Слайс — O(n)
for _, v := range slice {
    if v == target { break }
}
// Map — O(1)
val, ok := m[key]

На практике для маленьких коллекций (до ~8 элементов) слайс может быть быстрее из-за кеш-локальности. Но с ростом данных map выигрывает кратно. Если нужно часто проверять наличие элемента — используй map[T]struct{}.