Какая сложность поиска элемента в массиве

Поиск элемента в массиве зависит от условий:

1. Неотсортированный массив
   В худшем случае нужно проверить все элементы — сложность O(n).
   python

   Копировать

   def linear_search(arr, target):
       for i, item in enumerate(arr):
           if item == target:
               return i
       return -1

2. Отсортированный массив
   Можно использовать бинарный поиск — сложность O(log n).

   python

   Копировать

   def binary_search(arr, target):
       left, right = 0, len(arr) - 1
       while left <= right:
           mid = (left + right) // 2
           if arr[mid] == target:
               return mid
           elif arr[mid] < target:
               left = mid + 1
           else:
               right = mid - 1
       return -1

3. Хэш-таблица (set/dict)
   Поиск за O(1) в среднем случае, но требует дополнительной памяти.

   python

   Копировать

   my_set = {1, 2, 3}
   if 2 in my_set:  # O(1)
       print("Found")