📘 TypeScript

Алгоритмы поиска в TypeScript: подробное руководство

Урок 30 / 35 • Полная теория для чтения

Что это такое и зачем? (аналогия из реальной жизни)

Представьте, что вы пришли в огромную библиотеку. В ней тысячи книг, расставленных на стеллажах. Вам нужно найти книгу «Приключения Тома Сойера». Как вы будете её искать?

Первый способ — самый простой: вы подходите к первому стеллажу и начинаете просматривать каждую книгу подряд. Вы смотрите на корешок первой книги, потом второй, третьей... Пока не найдёте нужную. Это займёт много времени, но рано или поздно вы её найдёте (если она вообще есть в библиотеке). Такой способ называется линейным поиском.

Второй способ — хитрее. Вы идёте к библиотекарю и спрашиваете: «Где находятся книги на букву "П"?» Библиотекарь говорит: «На третьем стеллаже, секция 2». Вы идёте туда, берёте книгу из середины секции, смотрите — это «Приключения Шерлока Холмса». Вы понимаете, что «Том Сойер» должен быть раньше по алфавиту, поэтому вы ищете в левой части секции. Снова берёте книгу из середины — «Принц и нищий». Теперь вы знаете, что «Том Сойер» должен быть правее. Так, отбрасывая половину книг на каждом шаге, вы очень быстро находите нужную. Это — бинарный поиск.

Алгоритмы поиска — это способы найти элемент в наборе данных. Они повсюду: в поисковых системах (Google, Яндекс), в базах данных, в вашем телефоне, когда вы ищете контакт в списке друзей.

Зачем их изучать? Представьте, что у вас есть список из миллиона имён. Линейный поиск в худшем случае проверит миллион элементов. Бинарный поиск — всего 20! Разница между «подождать секунду» и «подождать час» — это разница между правильным и неправильным алгоритмом.

В этой статье мы разберём два основных алгоритма поиска на языке TypeScript: линейный (последовательный) и бинарный (двоичный). Вы узнаете, как они работают, когда какой применять, и научитесь писать код, который не стыдно показать на собеседовании.

Теория: как это работает изнутри

Линейный поиск (Linear Search)

Суть: Проходим по массиву от начала до конца и сравниваем каждый элемент с искомым.

Как работает:

Берём первый элемент массива.
Сравниваем его с тем, что ищем.
Если совпало — возвращаем индекс (или сам элемент).
Если нет — переходим к следующему.
Если дошли до конца и ничего не нашли — возвращаем -1 (или null).

Сложность: O(n) — «О большое от n». Это значит, что время поиска растёт прямо пропорционально количеству элементов. Если элементов в 2 раза больше — времени нужно в 2 раза больше.

Когда использовать:

Массив не отсортирован (бинарный поиск не работает).
Массив очень маленький (до 100 элементов).
Нужно найти все вхождения элемента (не только первое).

Бинарный поиск (Binary Search)

Суть: Делим отсортированный массив пополам и сравниваем искомый элемент с серединой. Если искомый меньше — ищем в левой половине, если больше — в правой. Повторяем, пока не найдём или не останется пустой диапазон.

Как работает:

Определяем левую границу (начало массива) и правую (конец массива).
Находим середину: (левая + правая) / 2.
Сравниваем элемент в середине с искомым:
- Если равны — нашли, возвращаем индекс.
- Если искомый меньше — сдвигаем правую границу на середину - 1.
- Если искомый больше — сдвигаем левую границу на середину + 1.
Повторяем шаги 2-3, пока левая граница не станет больше правой.

Сложность: O(log n) — логарифмическая. Если элементов 1024, нужно всего 10 сравнений (2^10 = 1024). Если 1 000 000 — 20 сравнений.

Важнейшее условие: Массив обязательно должен быть отсортирован по возрастанию (или убыванию). Если массив не отсортирован — бинарный поиск выдаст мусор.

Запомните: бинарный поиск — это как игра «Угадай число» от 1 до 100. Вы говорите «50», вам отвечают «больше» или «меньше». С каждым ходом вы отбрасываете половину вариантов.

Синтаксис в TypeScript: все формы и варианты

TypeScript — это надстройка над JavaScript, которая добавляет типы. Это значит, что мы можем указать, с какими данными работаем: числами, строками или чем-то ещё. Для алгоритмов поиска это особенно полезно — мы сразу видим, что функция ожидает массив чисел и возвращает число.

Базовая сигнатура функции линейного поиска

// Функция принимает массив чисел и искомое число
// Возвращает индекс элемента или -1, если не найден
function linearSearch(arr: number[], target: number): number {
    // ... тело функции
}

Базовая сигнатура функции бинарного поиска

// Функция принимает ОТСОРТИРОВАННЫЙ массив чисел и искомое число
// Возвращает индекс элемента или -1, если не найден
function binarySearch(sortedArr: number[], target: number): number {
    // ... тело функции
}

Обобщённые типы (Generics)

Мы можем сделать функцию универсальной — работающей с любыми типами данных, которые можно сравнивать:

// T — это обобщённый тип (любой тип)
// Мы говорим: "T должен быть таким, что его можно сравнивать"
function linearSearchGeneric<T>(arr: T[], target: T): number {
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === target) {
            return i;
        }
    }
    return -1;
}

// Теперь можно искать и числа, и строки:
const numbers = [1, 5, 3, 8, 2];
const strings = ["яблоко", "банан", "вишня"];

console.log(linearSearchGeneric(numbers, 3));    // 2
console.log(linearSearchGeneric(strings, "банан")); // 1

Методы массивов JavaScript, которые уже реализуют поиск

В TypeScript (и JavaScript) есть встроенные методы для поиска. Полезно знать их, но для понимания алгоритмов важно уметь написать их вручную.

Метод	Что делает	Возвращает	Пример
`indexOf()`	Ищет элемент в массиве (линейно)	Индекс первого вхождения или -1	`[1,2,3].indexOf(2) // 1`
`find()`	Ищет первый элемент, удовлетворяющий условию	Сам элемент или undefined	`[1,2,3].find(x => x > 1) // 2`
`findIndex()`	Ищет индекс первого элемента, удовлетворяющего условию	Индекс или -1	`[1,2,3].findIndex(x => x > 1) // 1`
`includes()`	Проверяет, есть ли элемент в массиве	true или false	`[1,2,3].includes(2) // true`
`filter()`	Находит ВСЕ элементы, удовлетворяющие условию	Новый массив с найденными элементами	`[1,2,3,2].filter(x => x === 2) // [2, 2]`

Важно: встроенные методы — это «чёрный ящик». Они работают быстро, но если вы не знаете, как они устроены внутри, вы не сможете выбрать правильный алгоритм для нестандартной задачи.

Примеры кода — от простого к сложному

Пример 1: Линейный поиск — самый простой вариант

/**
 * Линейный поиск числа в массиве.
 * Проходим по всем элементам, пока не найдём нужный.
 * 
 * @param arr - массив чисел (может быть не отсортирован)
 * @param target - число, которое ищем
 * @returns индекс найденного элемента или -1
 */
function linearSearchSimple(arr: number[], target: number): number {
    // Проходим по массиву от начала до конца
    for (let i = 0; i < arr.length; i++) {
        // Сравниваем текущий элемент с искомым
        if (arr[i] === target) {
            // Нашли! Возвращаем индекс
            return i;
        }
    }
    // Если прошли весь массив и не нашли — возвращаем -1
    return -1;
}

// Проверяем работу:
const myArray = [10, 25, 3, 47, 18, 99, 5];
const result = linearSearchSimple(myArray, 47);
console.log(`Индекс числа 47: ${result}`); // Индекс числа 47: 3

const notFound = linearSearchSimple(myArray, 100);
console.log(`Индекс числа 100: ${notFound}`); // Индекс числа 100: -1

Объяснение: Цикл for проходит по каждому индексу от 0 до последнего. Если нашли совпадение — сразу выходим из функции через return. Если цикл закончился — значит, элемента нет.

Пример 2: Линейный поиск с ранним выходом (оптимизация)

/**
 * Линейный поиск с проверкой на пустой массив.
 * Если массив пустой — сразу возвращаем -1, не тратим время.
 */
function linearSearchEarlyExit(arr: number[], target: number): number {
    // Проверяем, не пустой ли массив
    if (arr.length === 0) {
        return -1; // В пустом массиве ничего нет
    }

    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === target) {
            return i;
        }
    }
    return -1;
}

console.log(linearSearchEarlyExit([], 5)); // -1 (мгновенно)
console.log(linearSearchEarlyExit([1, 2, 3], 2)); // 1

Объяснение: Добавили проверку на пустой массив. Это мелочь, но в больших системах такие проверки экономят ресурсы.

Пример 3: Поиск всех вхождений (возвращаем массив индексов)

/**
 * Находит ВСЕ индексы, где встречается искомый элемент.
 * Полезно, если в массиве есть дубликаты.
 * 
 * @param arr - массив чисел
 * @param target - искомое число
 * @returns массив индексов (может быть пустым)
 */
function findAllOccurrences(arr: number[], target: number): number[] {
    const indices: number[] = []; // Создаём пустой массив для результатов

    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === target) {
            indices.push(i); // Добавляем индекс в массив
        }
    }

    return indices; // Возвращаем все найденные индексы
}

const data = [1, 3, 5, 3, 7, 3, 9];
console.log(findAllOccurrences(data, 3)); // [1, 3, 5] — три раза встретилось
console.log(findAllOccurrences(data, 10)); // [] — пустой массив

Объяснение: Вместо того чтобы останавливаться на первом совпадении, мы продолжаем поиск и собираем все индексы в массив. Это классический пример, когда одного indexOf недостаточно.

Пример 4: Бинарный поиск — итеративный вариант (цикл while)

/**
 * Бинарный поиск в ОТСОРТИРОВАННОМ массиве.
 * Используем цикл while — самый распространённый способ.
 * 
 * @param sortedArr - ОБЯЗАТЕЛЬНО отсортированный по возрастанию массив
 * @param target - искомое число
 * @returns индекс элемента или -1
 */
function binarySearchIterative(sortedArr: number[], target: number): number {
    let left = 0;                    // Левая граница поиска (начало массива)
    let right = sortedArr.length - 1; // Правая граница поиска (конец массива)

    // Пока левая граница не перешла через правую — ищем
    while (left <= right) {
        // Находим середину. Math.floor округляет вниз, чтобы получить целое число
        const mid = Math.floor((left + right) / 2);
        
        // Получаем значение в середине
        const midValue = sortedArr[mid];

        if (midValue === target) {
            // Ура! Нашли!
            return mid;
        } else if (midValue < target) {
            // Если значение в середине МЕНЬШЕ искомого,
            // значит искомое находится ПРАВЕЕ (в больших числах)
            // Сдвигаем левую границу за середину
            left = mid + 1;
        } else {
            // Если значение в середине БОЛЬШЕ искомого,
            // значит искомое находится ЛЕВЕЕ (в меньших числах)
            // Сдвигаем правую границу перед серединой
            right = mid - 1;
        }
    }

    // Если вышли из цикла — элемент не найден
    return -1;
}

// Тестируем на отсортированном массиве:
const sortedNumbers = [2, 5, 8, 12, 16, 23, 38, 45, 56, 72];
console.log(binarySearchIterative(sortedNumbers, 23)); // 5
console.log(binarySearchIterative(sortedNumbers, 1));  // -1 (меньше минимального)
console.log(binarySearchIterative(sortedNumbers, 100)); // -1 (больше максимального)

Объяснение: Это классическая реализация. Обратите внимание на условие while (left <= right). Если написать left < right — алгоритм может пропустить элемент, когда left и right указывают на один и тот же элемент.

Пример 5: Бинарный поиск — рекурсивный вариант

/**
 * Бинарный поиск через рекурсию (функция вызывает саму себя).
 * Элегантно, но может быть медленнее из-за вызовов функций.
 * 
 * @param sortedArr - отсортированный массив
 * @param target - искомое число
 * @param left - левая граница (по умолчанию 0)
 * @param right - правая граница (по умолчанию последний индекс)
 * @returns индекс элемента или -1
 */
function binarySearchRecursive(
    sortedArr: number[], 
    target: number, 
    left: number = 0, 
    right: number = sortedArr.length - 1
): number {
    // Базовый случай: если границы сошлись — элемент не найден
    if (left > right) {
        return -1;
    }

    // Находим середину
    const mid = Math.floor((left + right) / 2);
    const midValue = sortedArr[mid];

    if (midValue === target) {
        return mid; // Нашли!
    } else if (midValue < target) {
        // Ищем в правой половине (рекурсивный вызов)
        return binarySearchRecursive(sortedArr, target, mid + 1, right);
    } else {
        // Ищем в левой половине (рекурсивный вызов)
        return binarySearchRecursive(sortedArr, target, left, mid - 1);
    }
}

// Тестируем:
const arr = [1, 3, 5, 7, 9, 11, 13];
console.log(binarySearchRecursive(arr, 7));  // 3
console.log(binarySearchRecursive(arr, 2));  // -1

Объяснение: Рекурсия — это когда функция вызывает саму себя с новыми границами. Важно иметь базовый случай (условие выхода), иначе будет бесконечный цикл и переполнение стека.

Пример 6: Поиск первого и последнего вхождения (бинарный поиск с модификацией)

/**
 * Находит первое вхождение элемента в отсортированном массиве.
 * Даже если элемент найден, продолжаем искать левее.
 */
function findFirstOccurrence(sortedArr: number[], target: number): number {
    let left = 0;
    let right = sortedArr.length - 1;
    let result = -1; // Храним результат

    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        
        if (sortedArr[mid] === target) {
            result = mid;      // Запоминаем индекс
            right = mid - 1;   // Продолжаем искать в левой части
        } else if (sortedArr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return result;
}

/**
 * Находит последнее вхождение элемента в отсортированном массиве.
 * Даже если элемент найден, продолжаем искать правее.
 */
function findLastOccurrence(sortedArr: number[], target: number): number {
    let left = 0;
    let right = sortedArr.length - 1;
    let result = -1;

    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        
        if (sortedArr[mid] === target) {
            result = mid;      // Запоминаем индекс
            left = mid + 1;    // Продолжаем искать в правой части
        } else if (sortedArr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return result;
}

// Массив с дубликатами (обязательно отсортирован!)
const duplicates = [1, 2, 3, 3, 3, 4, 5, 6, 6, 7];

console.log(`Первое вхождение 3: ${findFirstOccurrence(duplicates, 3)}`);  // 2
console.log(`Последнее вхождение 3: ${findLastOccurrence(duplicates, 3)}`); // 4
console.log(`Первое вхождение 6: ${findFirstOccurrence(duplicates, 6)}`);  // 7
console.log(`Последнее вхождение 6: ${findLastOccurrence(duplicates, 6)}`); // 8

Объяснение: Модифицированный бинарный поиск. Когда находим элемент, не останавливаемся, а продолжаем искать в нужную сторону. Это позволяет найти границы диапазона одинаковых элементов.

Пример 7: Поиск в массиве объектов (по полю)

/**
 * Поиск пользователя по ID в массиве объектов.
 * Массив отсортирован по ID (по возрастанию).
 */

// Определяем тип данных
interface User {
    id: number;
    name: string;
    age: number;
}

// Массив пользователей, отсортированный по id
const users: User[] = [
    { id: 1, name: "Анна", age: 25 },
    { id: 3, name: "Борис", age: 30 },
    { id: 5, name: "Виктор", age: 22 },
    { id: 7, name: "Галина", age: 28 },
    { id: 9, name: "Дмитрий", age: 35 },
];

/**
 * Бинарный поиск пользователя по ID.
 * Используем обобщённый тип, но сравниваем по конкретному полю.
 */
function findUserById(sortedUsers: User[], targetId: number): User | null {
    let left = 0;
    let right = sortedUsers.length - 1;

    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        const midUser = sortedUsers[mid];

        if (midUser.id === targetId) {
            return midUser; // Возвращаем найденный объект
        } else if (midUser.id < targetId) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return null; // Не нашли — возвращаем null
}

const foundUser = findUserById(users, 5);
if (foundUser) {
    console.log(`Найден пользователь: ${foundUser.name}, возраст ${foundUser.age}`);
    // Найден пользователь: Виктор, возраст 22
} else {
    console.log("Пользователь не найден");
}

const notFoundUser = findUserById(users, 4);
console.log(notFoundUser); // null

Объяснение: В реальных проектах мы редко ищем просто числа. Чаще — объекты по какому-то полю (ID, дата, название). Здесь мы используем интерфейс TypeScript для типизации и ищем по полю id.

Сравнение с Python: чем похоже и чем отличается

Python — ещё один популярный язык для изучения алгоритмов. Давайте сравним, как выглядят алгоритмы поиска на Python и TypeScript.

Аспект	TypeScript	Python
Типизация	Статическая (указываем типы: `number[]`, `: number`)	Динамическая (типы не указываем, но можно добавить аннотации)
Цикл for	`for (let i = 0; i < arr.length; i++)`	`for i in range(len(arr)):` или `for value in arr:`
Встроенный поиск	`arr.indexOf(target)`	`arr.index(target)` (вызывает исключение, если не найдено)
Проверка наличия	`arr.includes(target)`	`target in arr` (для списков — линейный поиск)
Бинарный поиск (стандартная библиотека)	Нет встроенного. Нужно писать самому или использовать сторонние библиотеки.	`bisect` модуль: `bisect_left(arr, target)`
Синтаксис функций	`function name(params): ReturnType { ... }`	`def name(params): ...`
null vs None	`null` или `-1` для обозначения «не найдено»	`None` или `-1`

Пример линейного поиска на Python для сравнения:

// TypeScript
function linearSearchTS(arr: number[], target: number): number {
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === target) {
            return i;
        }
    }
    return -1;
}

# Python (для сравнения)
def linear_search_py(arr, target):
    for i, value in enumerate(arr):
        if value == target:
            return i
    return -1

Ключевые отличия:

В Python нет фигурных скобок — используются отступы.
В Python нет let и const — переменные объявляются просто именем.
В Python функция enumerate даёт сразу индекс и значение — в TS нужно писать arr[i].
TypeScript требует указания типов — это помогает избежать ошибок на этапе компиляции.

Совет: Если вы знаете Python, вы легко выучите TypeScript и наоборот. Главное — понять логику алгоритма, а синтаксис — дело привычки.

Типичные ошибки и подводные камни

Ошибка 1: Забыть отсортировать массив для бинарного поиска

const unsorted = [5, 2, 8, 1, 9, 3];
// Забыли отсортировать!
console.log(binarySearchIterative(unsorted, 8)); 
// Может вернуть -1, хотя 8 есть в массиве!

Почему: Бинарный поиск работает только на отсортированных данных. Если массив не отсортирован, алгоритм будет отбрасывать не ту половину.

Ошибка 2: Ошибка на единицу (off-by-one error)

// НЕПРАВИЛЬНО: условие left < right (без равно)
function wrongBinarySearch(arr: number[], target: number): number {
    let left = 0;
    let right = arr.length - 1;
    
    while (left < right) { // ОШИБКА! Должно быть <=
        const mid = Math.floor((left + right) / 2);
        if (arr[mid] === target) return mid;
        if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

// Пример: массив из одного элемента
console.log(wrongBinarySearch([5], 5)); // -1 (не найдёт!)

Почему: Когда left === right, цикл не выполняется, и мы пропускаем последний элемент. Всегда используйте left <= right.

Ошибка 3: Переполнение при вычислении середины

// Потенциально опасный способ (для очень больших массивов)
const mid = Math.floor((left + right) / 2);
// Если left и right — огромные числа (например, 2^31), их сумма может превысить 
// максимальное безопасное целое число в JavaScript (Number.MAX_SAFE_INTEGER)

// Безопасный способ:
const mid = left + Math.floor((right - left) / 2);

Когда это важно: В учебных примерах — никогда. Но в продакшене с массивами на миллиарды элементов — критично.

Ошибка 4: Путаница между indexOf и find

const items = [1, 2, 3, 4, 5];

// indexOf ищет по значению
console.log(items.indexOf(3)); // 2

// find ищет по условию (функция)
console.log(items.find(x => x > 3)); // 4 (первый элемент, удовлетворяющий условию)

// Частая ошибка: передать значение в find
console.log(items.find(3)); // Ошибка! 3 — это не функция

Ошибка 5: Не учитывать, что массив может быть пустым

function searchInEmptyArray(arr: number[], target: number): number {
    // Если не проверить длину, то arr[0] будет undefined
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === target) {
            return i;
        }
    }
    return -1; // Для пустого массива цикл просто не выполнится — это корректно
}

// А вот бинарный поиск без проверки упадёт:
function badBinarySearch(arr: number[], target: number): number {
    let left = 0;
    let right = arr.length - 1; // right = -1 для пустого массива
    while (left <= right) { // 0 <= -1 — false, цикл не выполнится
        // ...
    }
    return -1; // Вернёт -1, что корректно
}
// Но если мы не проверим длину и попробуем обратиться к arr[0] — получим undefined

Лучшие практики и советы профессионалов

1. Всегда проверяйте граничные случаи

Перед тем как сдать код, проверьте:

Пустой массив
Массив из одного элемента
Искомый элемент — первый

← Предыдущая Алгоритмы сортировки в TypeScript: подробное руков Вперёд → Паттерны проектирования в TypeScript: подробное ру