Алгоритмы с нуля

Обход массива

Суть Обход означает посещение каждого элемента массива, и это единственно самая частая операция, которую ты будешь делать. Научись формам цикла, приёмам (накопление, поиск, преобразование, проверка), раннему выходу и обратному ходу.

◷ 16 min

У тебя есть массив чисел и нужно обработать каждое. Начинаешь с индекса 0, переходишь на 1, потом 2, и так до конца. Это простое путешествие — посещение каждого элемента по очереди — и есть обход. Это основа почти каждого алгоритма, что ты напишешь.

Цель

После этого урока ты сможешь обойти массив циклом for, узнать частые приёмы обхода (накопление, поиск, преобразование, проверка), разобраться, когда использовать индекс vs значение, применить ранний выход (остановку, как только ответ известен), обойти два массива вместе и идти по массиву с конца к началу.

Идея

Обход — это акт посещения каждого элемента массива в определённом порядке, обычно с начала к концу. Самый простой цикл обхода:

for (let i = 0; i < arr.length; i++) {
  // Обработай arr[i]
}

Этот цикл посещает каждый элемент ровно один раз, от индекса 0 до arr.length - 1. Это O(n), потому что ты касаешься каждого элемента.

Пять приёмов обхода:

Накопление (сумма, произведение, счёт) — инициализируй аккумулятор перед циклом, обновляй его с каждым элементом, верни после цикла.
Поиск (первое совпадение, максимум, минимум) — сканируй массив, пока условие не выполнится, верни результат.
Преобразование (построение нового массива) — во время обхода строй новый массив, применяя функцию к каждому элементу.
Проверка (есть ли элемент, удовлетворяющий условию? все ли элементы его удовлетворяют?) — сканируй и верни true/false, когда ответ ясен.
Ранний выход — остановись, как только ты знаешь ответ, не посещая оставшиеся элементы.

Индекс vs значение:

Когда ты пишешь for (let i = 0; i < arr.length; i++), ты итерируешь с индексом i. Внутри цикла ты получаешь значение через arr[i]. Иногда нужен индекс (чтобы менять массив, отслеживать позицию), иногда только значение. JavaScript предлагает цикл for...of для получения только значений:

for (let value of arr) {
  // Обработай value напрямую
}

Но если нужен индекс (менять элементы, знать позицию), нужен цикл с индексом.

Ранний выход и лучший/худший случай:

Когда ты ищешь значение и возвращаешься сразу при нахождении, ты применяешь ранний выход. Это меняет лучший и худший случаи:

Лучший случай: найдено на индексе 0 → 1 шаг → O(1)
Худший случай: не найдено (проверяешь все n) → n шагов → O(n)
Big-O: всё ещё O(n), потому что анализируем худший случай

Ранний выход не меняет Big-O, но меняет реальную производительность. Для лучшего случая ты можешь быть намного быстрее.

Обратный ход:

Начни с конца и двигайся к началу:

for (let i = arr.length - 1; i >= 0; i--) {
  // Обработай arr[i] с конца к началу
}

Частая ошибка: начало с arr.length вместо arr.length - 1. Последний действительный индекс — это arr.length - 1.

Обход двух массивов вместе:

Если у тебя два массива одной длины, ты можешь итерировать оба параллельно:

for (let i = 0; i < arr1.length; i++) {
  // Обработай arr1[i] и arr2[i] вместе
}

Код

Запрограммируем пять приёмов обхода и ранний выход:

1. Накопление (сумма):

function sum(arr) {
  let total = 0;  // Инициализируй аккумулятор
  for (let i = 0; i < arr.length; i++) {
    total += arr[i];  // Добавь каждый элемент
  }
  return total;  // Верни накопленное значение
}

2. Поиск (первый индекс значения, или -1, если не найдено):

function indexOf(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) {
      return i;  // Ранний выход: нашли
    }
  }
  return -1;  // Дошли до конца без находки
}

3. Преобразование (удвой каждый элемент):

function doubled(arr) {
  let result = [];  // Построй новый массив
  for (let i = 0; i < arr.length; i++) {
    result.push(arr[i] * 2);  // Преобразуй каждый элемент
  }
  return result;
}

4. Проверка (есть ли в массиве отрицательное число?):

function hasNegative(arr) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] < 0) {
      return true;  // Ранний выход: ответ да
    }
  }
  return false;  // Отрицательных не найдено
}

5. Счёт совпадающих элементов:

function countMatching(arr, predicate) {
  let count = 0;
  for (let i = 0; i < arr.length; i++) {
    if (predicate(arr[i])) {
      count++;
    }
  }
  return count;
}

Попробуй запустить:

Вывод

Пошаговый разбор

Давай трассируем indexOf (поиск) с ранним выходом. Ищем значение 5 в [1, 7, 5, 3]:


      1
      function indexOf(arr, target) {
    

      2
        for (let i = 0; i < arr.length; i++) {
    

      3
          if (arr[i] === target) {
    

      4
            return i;
    

      5
          }
    

      6
        }
    

      7
        return -1;
    

      8
      }

Сложность

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

Но ранний выход меняет лучший случай:

Операция	Лучший случай	Средний случай	Худший случай	Big-O
Сумма всех элементов	O(n)	O(n)	O(n)	O(n)
Поиск значения (ранний выход)	O(1) найдено в начале	O(n/2)	O(n) не найдено	O(n)
Проверка, есть ли отрицательное (ранний выход)	O(1) найдено в начале	O(n/2)	O(n) не найдено	O(n)
Счёт совпадений	O(n)	O(n)	O(n)	O(n)
Преобразование (строит новый массив)	O(n)	O(n)	O(n)	O(n)

Ключевая идея: Ранний выход может дать намного более быструю реальную производительность в лучшем случае, хотя Big-O анализ сосредоточен на худшем случае. На собеседованиях ты можешь произвести впечатление, заметив: “Это O(n) в худшем случае, но O(1), если ответ найдён сразу.”

Практика 0 / 5

Напиши функцию, которая найдёт максимальное значение в [3, 7, 2, 9, 1]. Чему равен максимум?

Сколько шагов делает indexOf в худшем случае, если цель не найдена в массиве из 100 элементов?

Когда ты обходишь массив и нужно менять каждый элемент (например, умножить на 2), почему тебе нужен индекс, а не только значение?

Какова временная сложность функции, что суммирует все элементы в массиве из n элементов?

Расставь эти шаги для обхода массива в обратном направлении с индекса 4 (предполагая, массив из 5 элементов):

Начни цикл: i = 4
Декремент i (i--)
Проверь условие: i >= 0
Обработай arr[i]

Граничные случаи

Пустые массивы. Если входной массив пусто, цикл for (let i = 0; i < arr.length; i++) никогда не выполняется (потому что 0 < 0 ложно). Для приёмов вроде суммы и счёта, возврат 0 правилен. Для приёмов вроде поиска и максимума, возврат -1 или null разумен (максимума пустого массива нет). Всегда думай о граничных случаях.

Частая ошибка

Ошибки на один в обратном ходе. Самая частая ошибка — начать с i = arr.length (что вне границ) вместо i = arr.length - 1. Последний действительный индекс всегда arr.length - 1. Протестируй на малом массиве: [1, 2, 3] имеет длину 3, и последний индекс 2. Начни обратный цикл с 2, не с 3.

Проверь себя

Викторина

Почему функция поиска, что возвращается, как только найдена цель (ранний выход), всё ещё имеет O(n) Big-O временную сложность?

Итог

Обход — это посещение каждого элемента в массиве, обычно с начала к концу. Ключевые концепции:

Базовый цикл: for (let i = 0; i < arr.length; i++) посещает каждый элемент за O(n) времени.
Пять приёмов:
- Накопление: инициализируй, обновляй, верни
- Поиск: верни, когда условие выполнено
- Преобразование: построй новый массив
- Проверка: верни true/false, когда ответ известен
- Счёт: инкрементируй счётчик
Индекс vs значение: Используй цикл с индексом, если нужна позиция или модификация. Используй for...of для получения только значений.
Ранний выход: Возвращайся сразу, когда ответ найден. Улучшает лучший случай, но не меняет Big-O (всё ещё O(n) в худшем случае).
Обратный ход: Начни с arr.length - 1, используй i >= 0, декремент с i--. Частая ошибка: начало с arr.length.
Два массива вместе: Итерируй по индексам и обрабатывай оба массива параллельно.

Обход — это основа почти каждого алгоритма на массивах, что ты напишешь. Овладей этими формами сейчас; ты будешь их переиспользовать тысячи раз.

Продолжить восхождение ↑Два указателя