Приведи пример алгоритма и объясни его алгоритмическую сложность.

Алгоритм: Бинарный поиск в отсортированном списке.

Сложность: O(log n) по времени в худшем и среднем случае. O(1) по памяти (итеративная реализация).

Реализация на Dart:

/// Возвращает индекс [target] в отсортированном списке [sortedList].
/// Возвращает -1, если элемент не найден.
int binarySearch(List<int> sortedList, int target) {
  int low = 0;
  int high = sortedList.length - 1;

  while (low <= high) {
    // Избегаем переполнения для больших списков.
    int mid = low + ((high - low) ~/ 2);
    int midValue = sortedList[mid];

    if (midValue == target) {
      return mid; // Элемент найден.
    } else if (midValue < target) {
      low = mid + 1; // Ищем в правой половине.
    } else {
      high = mid - 1; // Ищем в левой половине.
    }
  }
  return -1; // Элемент отсутствует.
}

void main() {
  final list = [1, 3, 5, 7, 9, 11, 13];
  print(binarySearch(list, 7)); // 3
  print(binarySearch(list, 10)); // -1
}

Почему O(log n)? Алгоритм на каждом шаге делит область поиска пополам. В худшем случае он сделает столько делений, сколько раз n можно разделить на 2, пока не останется 1 элемент. Это и есть логарифм по основанию 2: log₂(n). Например, для списка из 1024 элементов потребуется не более 10 проверок (т.к. 2¹⁰ = 1024).

Ключевое условие: Список должен быть отсортирован. Для несортированного списка бинарный поиск неприменим, и потребуется линейный поиск со сложностью O(n).