Какова временная сложность поиска элемента в слайсе (slice)?

Временная сложность поиска в слайсе зависит от того, отсортирован он или нет.

• Линейный поиск (для неупорядоченных слайсов): O(n) Это стандартный способ поиска, требующий перебора всех элементов до нахождения нужного. В худшем случае придётся проверить весь слайс.

  // Линейный поиск
  func linearSearch(slice []int, target int) bool {
      for _, v := range slice {
          if v == target {
              return true
          }
      }
      return false
  }

• Бинарный поиск (для отсортированных слайсов): O(log n) Если слайс предварительно отсортирован, можно применить значительно более быстрый бинарный поиск. В Go для этого есть удобная функция sort.SearchInts.

  // Бинарный поиск
  func binarySearch(sortedSlice []int, target int) bool {
      // Важно: слайс должен быть уже отсортирован
      // sort.Ints(slice) 
      i := sort.SearchInts(sortedSlice, target)
      // Проверяем, что элемент найден, а не просто найдена позиция для вставки
      return i < len(sortedSlice) && sortedSlice[i] == target
  }

Важное замечание: Если операции поиска выполняются часто, лучшей структурой данных будет map, которая обеспечивает среднюю сложность поиска O(1).