Базовые алгоритмы

Линейный поиск, бинарный поиск и сортировка — три фундаментальных алгоритма которые надо знать.

Шаг 1 из 3Практика

Линейный поиск

Самый простой алгоритм поиска

Линейный поиск — это когда ты перебираешь все элементы по одному, пока не найдёшь нужный (или не убедишься что его нет).

Аналогия из жизни: ищешь нужную книгу в стопке — берёшь каждую и смотришь название, пока не найдёшь.

javascript

// Найти индекс числа в массиве
function linearSearch(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) {
      return i;  // нашли — возвращаем индекс
    }
  }
  return -1;  // не нашли — возвращаем -1
}

const numbers = [3, 7, 12, 31, 56, 89];
linearSearch(numbers, 31);  // 3 (индекс)
linearSearch(numbers, 99);  // -1 (не нашли)

Когда применять

Плюсы:

Работает с любым массивом — неотсортированным, строками, объектами
Простой код — легко написать и понять
Для маленьких массивов (до ~50 элементов) — достаточно быстрый

Минусы:

Медленный на больших данных
В худшем случае перебираем все элементы

Сложность: O(n)

javascript

Массив из 10 элементов   → до 10 проверок
Массив из 1 000          → до 1 000 проверок
Массив из 1 000 000      → до 1 000 000 проверок

Время растёт пропорционально размеру — это и есть O(n).

Частный случай: indexOf

В JavaScript не нужно писать линейный поиск вручную — массивы имеют встроенные методы:

javascript

const fruits = ["яблоко", "банан", "груша", "манго"];

fruits.indexOf("груша")       // 2 — индекс или -1
fruits.includes("банан")      // true — просто да/нет
fruits.find(f => f.length > 5)   // "яблоко" — первый подходящий элемент
fruits.findIndex(f => f === "манго")  // 3 — индекс найденного

Все они работают как линейный поиск — O(n).

У тебя массив из 1000 элементов. В среднем сколько проверок сделает линейный поиск?

Алгоритмы и сложность (Big O)Схемы: бизнес-логика и блок-схемы алгоритмов

StudyCode

Самый простой алгоритм поиска

Аналогия из жизни: ищешь нужную книгу в стопке — берёшь каждую и смотришь название, пока не найдёшь.

javascript

// Найти индекс числа в массиве
function linearSearch(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) {
      return i;  // нашли — возвращаем индекс
    }
  }
  return -1;  // не нашли — возвращаем -1
}

const numbers = [3, 7, 12, 31, 56, 89];
linearSearch(numbers, 31);  // 3 (индекс)
linearSearch(numbers, 99);  // -1 (не нашли)

Когда применять

Плюсы:

Работает с любым массивом — неотсортированным, строками, объектами

Простой код — легко написать и понять

Для маленьких массивов (до ~50 элементов) — достаточно быстрый

Минусы:

Медленный на больших данных

В худшем случае перебираем все элементы

Сложность: O(n)

javascript

Массив из 10 элементов   → до 10 проверок
Массив из 1 000          → до 1 000 проверок
Массив из 1 000 000      → до 1 000 000 проверок

Время растёт пропорционально размеру — это и есть O(n).

Частный случай: indexOf

В JavaScript не нужно писать линейный поиск вручную — массивы имеют встроенные методы:

javascript

const fruits = ["яблоко", "банан", "груша", "манго"];

fruits.indexOf("груша")       // 2 — индекс или -1
fruits.includes("банан")      // true — просто да/нет
fruits.find(f => f.length > 5)   // "яблоко" — первый подходящий элемент
fruits.findIndex(f => f === "манго")  // 3 — индекс найденного

Все они работают как линейный поиск — O(n).