🐘 PHP

Algoritmos de busca em PHP: um guia completo

Lição 30 / 35 • Leitura completa da teoria

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

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

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

Второй способ (умный): Вы идёте к каталогу, где все книги отсортированы по алфавиту. Вы открываете раздел «Г», находите «Гарри Поттер» и сразу идёте к нужной полке. Это быстро и эффективно.

В программировании происходит то же самое. Алгоритмы поиска — это способы найти нужный элемент в массиве данных. От того, какой алгоритм вы выберете, зависит, сколько времени ваша программа потратит на поиск. Если данных мало (например, 10 книг), разница незаметна. Но если у вас миллион записей в базе данных, правильный алгоритм может ускорить работу в тысячи раз.

Важно: Алгоритмы поиска — это не просто «найти элемент». Это фундамент, на котором строятся базы данных, поисковые системы (Google, Яндекс), рекомендательные сервисы (Netflix, YouTube) и даже игры.

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

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

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

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

Визуализация: Представьте, что вы проверяете билеты в кинотеатре. Вы стоите у входа и смотрите билет каждого входящего зрителя. Вы не знаете, кто придёт первым, поэтому проверяете всех подряд. Как только находите нужного человека — останавливаетесь.

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

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

Массив небольшой (до 100-200 элементов)
Массив не отсортирован
Нужно найти все вхождения элемента (а не только первое)
Данные постоянно меняются (сортировать каждый раз дорого)

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

Принцип работы: Алгоритм работает только с отсортированными данными. Он делит массив пополам, сравнивает искомое значение с центральным элементом. Если искомое меньше центрального — поиск продолжается в левой половине. Если больше — в правой. Процесс повторяется, пока не останется один элемент.

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

Сложность: O(log n) — логарифмическая сложность. Это очень быстро. Если элементов 1 000 000, бинарному поиску нужно всего около 20 сравнений (потому что 2^20 ≈ 1 000 000). Линейному поиску в худшем случае потребовалось бы 1 000 000 сравнений.

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

Массив большой (от 1000 элементов)
Массив отсортирован (или его можно отсортировать один раз)
Поиск выполняется многократно (один раз отсортировали, много раз ищем)
Важна скорость выполнения

Ключевое отличие: Линейный поиск работает с любыми данными, но медленно. Бинарный — только с отсортированными, но очень быстро. Выбор алгоритма — это всегда компромисс между скоростью и подготовкой данных.

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

В PHP есть встроенные функции для поиска, но для понимания алгоритмов мы будем писать свои реализации. Это поможет вам понять, что происходит «под капотом».

Основные функции PHP для поиска

Функция	Что делает	Возвращает	Примечание
`in_array($needle, $haystack)`	Проверяет, есть ли значение в массиве	true/false	Линейный поиск внутри
`array_search($needle, $haystack)`	Ищет значение и возвращает его ключ	Ключ или false	Тоже линейный поиск
`array_key_exists($key, $array)`	Проверяет, существует ли ключ	true/false	Очень быстрый (хэш-таблицы)
`isset($array[$key])`	Проверяет, существует ли ключ и не null	true/false	Быстрее, чем array_key_exists

Важно: Встроенные функции PHP используют оптимизированный код на C. Они работают быстрее, чем ваши собственные реализации на PHP. Но для обучения и понимания алгоритмов мы будем писать свои версии.

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

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

<?php
/**
 * Функция линейного поиска
 * @param array $arr - массив, в котором ищем
 * @param mixed $target - значение, которое ищем
 * @return int|false - индекс элемента или false, если не найден
 */
function linearSearch($arr, $target) {
    // Проходим по всем элементам массива
    for ($i = 0; $i < count($arr); $i++) {
        // Сравниваем текущий элемент с искомым
        if ($arr[$i] === $target) {
            // Если нашли — возвращаем индекс
            return $i;
        }
    }
    // Если ничего не нашли — возвращаем false
    return false;
}

// Тестируем
$books = ["Война и мир", "Гарри Поттер", "Мастер и Маргарита", "Преступление и наказание"];
$result = linearSearch($books, "Гарри Поттер");
echo "Индекс найденного элемента: " . $result; // Выведет: 1
?>

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

Пример 2: Линейный поиск — поиск всех вхождений

<?php
/**
 * Поиск всех вхождений элемента в массиве
 * @param array $arr - массив для поиска
 * @param mixed $target - искомое значение
 * @return array - массив индексов всех найденных элементов
 */
function linearSearchAll($arr, $target) {
    $foundIndices = []; // Массив для хранения результатов
    
    for ($i = 0; $i < count($arr); $i++) {
        if ($arr[$i] === $target) {
            // Добавляем индекс в массив результатов
            $foundIndices[] = $i;
        }
    }
    
    return $foundIndices; // Возвращаем массив (может быть пустым)
}

// Тестируем
$numbers = [5, 3, 7, 3, 9, 3, 1, 3];
$result = linearSearchAll($numbers, 3);
echo "Индексы всех троек: " . implode(", ", $result); // Выведет: 1, 3, 5, 7
?>

Объяснение: В отличие от первого примера, мы не останавливаемся после первого совпадения. Мы собираем все индексы в массив $foundIndices. Функция implode превращает массив в строку для красивого вывода.

Пример 3: Линейный поиск — с подсчётом шагов

<?php
/**
 * Линейный поиск с подсчётом количества сравнений
 */
function linearSearchWithStats($arr, $target) {
    $comparisons = 0; // Счётчик сравнений
    
    for ($i = 0; $i < count($arr); $i++) {
        $comparisons++; // Увеличиваем счётчик при каждом сравнении
        if ($arr[$i] === $target) {
            echo "Потребовалось сравнений: $comparisons
";
            return $i;
        }
    }
    
    echo "Потребовалось сравнений: $comparisons
";
    return false;
}

// Тестируем
$data = range(1, 100); // Массив чисел от 1 до 100
$result = linearSearchWithStats($data, 50);
echo "Результат: " . ($result !== false ? "Найден на индексе $result" : "Не найден");
// Выведет: Потребовалось сравнений: 50
// Результат: Найден на индексе 49
?>

Объяснение: Этот пример наглядно показывает, почему линейный поиск медленный. Чтобы найти число 50 в массиве из 100 элементов, потребовалось 50 сравнений. А если бы мы искали 100 — потребовалось бы 100 сравнений.

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

<?php
/**
 * Бинарный поиск (итеративный)
 * @param array $arr - ОТСОРТИРОВАННЫЙ массив
 * @param mixed $target - искомое значение
 * @return int|false - индекс или false
 */
function binarySearch($arr, $target) {
    $left = 0; // Левая граница поиска
    $right = count($arr) - 1; // Правая граница поиска
    
    while ($left <= $right) {
        // Находим середину (целочисленное деление)
        $mid = floor(($left + $right) / 2);
        
        echo "Ищем между индексами $left и $right, середина = $mid
";
        
        if ($arr[$mid] === $target) {
            // Нашли! Возвращаем индекс
            return $mid;
        }
        
        if ($arr[$mid] < $target) {
            // Искомое больше середины — ищем в правой половине
            $left = $mid + 1;
        } else {
            // Искомое меньше середины — ищем в левой половине
            $right = $mid - 1;
        }
    }
    
    // Элемент не найден
    return false;
}

// Тестируем
$sortedNumbers = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100];
$result = binarySearch($sortedNumbers, 70);
echo "Результат: " . ($result !== false ? "Найден на индексе $result" : "Не найден");
?>

Объяснение: Мы устанавливаем левую и правую границы поиска. На каждом шаге находим середину. Если значение в середине равно искомому — отлично, нашли. Если искомое больше — сдвигаем левую границу за середину. Если меньше — сдвигаем правую. Процесс повторяется, пока границы не сомкнутся.

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

<?php
/**
 * Бинарный поиск (рекурсивный)
 * @param array $arr - отсортированный массив
 * @param mixed $target - искомое значение
 * @param int $left - левая граница (по умолчанию 0)
 * @param int $right - правая граница (по умолчанию последний индекс)
 * @return int|false - индекс или false
 */
function binarySearchRecursive($arr, $target, $left = 0, $right = null) {
    // Если правая граница не задана — устанавливаем её
    if ($right === null) {
        $right = count($arr) - 1;
    }
    
    // Базовый случай: границы сошлись — элемента нет
    if ($left > $right) {
        return false;
    }
    
    // Находим середину
    $mid = floor(($left + $right) / 2);
    
    if ($arr[$mid] === $target) {
        return $mid; // Нашли!
    }
    
    if ($arr[$mid] < $target) {
        // Ищем в правой половине
        return binarySearchRecursive($arr, $target, $mid + 1, $right);
    } else {
        // Ищем в левой половине
        return binarySearchRecursive($arr, $target, $left, $mid - 1);
    }
}

// Тестируем
$letters = ['а', 'б', 'в', 'г', 'д', 'е', 'ё', 'ж', 'з'];
$result = binarySearchRecursive($letters, 'ж');
echo "Результат: " . ($result !== false ? "Найден на индексе $result" : "Не найден");
?>

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

Пример 6: Сравнение скорости линейного и бинарного поиска

<?php
/**
 * Сравнение производительности двух алгоритмов
 */

// Создаём большой отсортированный массив
$size = 100000;
$bigArray = range(1, $size);

// Элемент, который будем искать (в самом конце)
$target = $size;

// Замеряем время линейного поиска
$start = microtime(true);
$resultLinear = linearSearch($bigArray, $target);
$timeLinear = microtime(true) - $start;

// Замеряем время бинарного поиска
$start = microtime(true);
$resultBinary = binarySearch($bigArray, $target);
$timeBinary = microtime(true) - $start;

echo "Размер массива: $size элементов
";
echo "Искомое значение: $target

";
echo "Линейный поиск:
";
echo "  Время: " . round($timeLinear, 6) . " секунд
";
echo "  Результат: " . ($resultLinear !== false ? "Найден" : "Не найден") . "

";
echo "Бинарный поиск:
";
echo "  Время: " . round($timeBinary, 6) . " секунд
";
echo "  Результат: " . ($resultBinary !== false ? "Найден" : "Не найден") . "

";
echo "Бинарный быстрее в " . round($timeLinear / $timeBinary, 0) . " раз!
";
?>

Объяснение: Этот пример наглядно демонстрирует разницу. На массиве из 100 000 элементов бинарный поиск будет работать в тысячи раз быстрее. Функция microtime(true) возвращает текущее время в секундах с высокой точностью.

Пример 7: Поиск в ассоциативном массиве

<?php
/**
 * Поиск в ассоциативном массиве (ключ-значение)
 */

// База данных студентов (ассоциативный массив)
$students = [
    'ivanov' => ['name' => 'Иван', 'age' => 20, 'grade' => 4.5],
    'petrov' => ['name' => 'Пётр', 'age' => 21, 'grade' => 3.8],
    'sidorov' => ['name' => 'Сидор', 'age' => 19, 'grade' => 5.0],
    'smirnov' => ['name' => 'Анна', 'age' => 22, 'grade' => 4.2],
];

/**
 * Поиск студента по логину
 * @param array $database - база данных
 * @param string $login - логин студента
 * @return array|null - данные студента или null
 */
function findStudentByLogin($database, $login) {
    // Проверяем, существует ли ключ в массиве
    if (array_key_exists($login, $database)) {
        return $database[$login];
    }
    return null;
}

/**
 * Поиск всех студентов с оценкой выше заданной
 * @param array $database - база данных
 * @param float $minGrade - минимальная оценка
 * @return array - массив найденных студентов
 */
function findStudentsByGrade($database, $minGrade) {
    $result = [];
    
    foreach ($database as $login => $data) {
        if ($data['grade'] >= $minGrade) {
            $result[$login] = $data;
        }
    }
    
    return $result;
}

// Тестируем
$student = findStudentByLogin($students, 'sidorov');
if ($student) {
    echo "Найден студент: " . $student['name'] . ", возраст: " . $student['age'] . "
";
}

$excellentStudents = findStudentsByGrade($students, 4.5);
echo "Отличники:
";
foreach ($excellentStudents as $login => $data) {
    echo "  - " . $data['name'] . " (логин: $login, оценка: " . $data['grade'] . ")
";
}
?>

Объяснение: Ассоциативные массивы в PHP реализованы как хэш-таблицы. Поиск по ключу (array_key_exists) происходит очень быстро — O(1). А вот поиск по значению (оценке) требует линейного прохода по всем элементам.

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

Характеристика	PHP	Python
Встроенная функция поиска	`in_array()`, `array_search()`	`in` (оператор), `list.index()`
Проверка существования ключа	`array_key_exists()`, `isset()`	`in` для словарей
Бинарный поиск в стандартной библиотеке	Нет встроенной (нужно писать самому)	`bisect` модуль
Синтаксис циклов	`for ($i = 0; $i < n; $i++)`	`for i in range(n)`
Возврат при ошибке	`false` или `null`	`-1` или исключение
Типизация	Динамическая (с версии 7.4 можно указывать типы)	Динамическая (с версии 3.5 можно аннотации)

Главное отличие: В Python есть встроенный модуль bisect для бинарного поиска. В PHP такой модуль отсутствует, поэтому разработчикам нужно либо писать свою реализацию, либо использовать сторонние библиотеки. Однако базовые принципы алгоритмов абсолютно одинаковы в обоих языках.

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

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

<?php
// НЕПРАВИЛЬНО: массив не отсортирован
$unsorted = [5, 2, 8, 1, 9, 3];
$result = binarySearch($unsorted, 8); // Может не найти или найти неправильно!
?>

Решение: Всегда проверяйте, что массив отсортирован перед бинарным поиском. Используйте sort() для сортировки.

Ошибка 2: Путаница между строгим и нестрогим сравнением

<?php
// Опасный момент
$arr = [0, "0", false, null];
var_dump(in_array(0, $arr)); // true (найдёт все, потому что 0 == false)
var_dump(in_array(0, $arr, true)); // true (строгое сравнение, найдёт только 0)
?>

Решение: Используйте третий параметр true в in_array() и array_search() для строгого сравнения (===).

Ошибка 3: Неправильная обработка результата

<?php
// ОПАСНО: false может быть преобразован в 0
$arr = [10, 20, 30];
$index = array_search(10, $arr); // Вернёт 0 (первый элемент)
if ($index == false) { // НЕПРАВИЛЬНО! 0 == false
    echo "Элемент не найден"; // Это сообщение НЕ выведется
}

// ПРАВИЛЬНО: используем строгое сравнение
if ($index === false) {
    echo "Элемент не найден";
}
?>

Решение: Всегда используйте === для проверки результата поиска, потому что индекс 0 в PHP преобразуется в false при нестрогом сравнении.

Ошибка 4: Бесконечный цикл в бинарном поиске

<?php
// НЕПРАВИЛЬНО: забыли обновить границы
function badBinarySearch($arr, $target) {
    $left = 0;
    $right = count($arr) - 1;
    
    while ($left <= $right) {
        $mid = floor(($left + $right) / 2);
        if ($arr[$mid] === $target) return $mid;
        // Забыли изменить left или right — бесконечный цикл!
    }
    return false;
}
?>

Решение: Всегда обновляйте $left или $right внутри цикла. Используйте $mid + 1 и $mid - 1, чтобы избежать зацикливания.

Ошибка 5: Игнорирование производительности

<?php
// ПЛОХО: каждый раз вызываем count() в условии цикла
for ($i = 0; $i < count($arr); $i++) {
    // ...
}

// ХОРОШО: сохраняем длину в переменную
$length = count($arr);
for ($i = 0; $i < $length; $i++) {
    // ...
}
?>

Решение: Для больших массивов сохраняйте результат count() в переменную, чтобы не вызывать функцию на каждой итерации.

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

Всегда выбирайте правильный алгоритм. Не используйте бинарный поиск для неотсортированных данных. Не используйте линейный поиск для больших отсортированных массивов.
Используйте встроенные функции PHP. in_array(), array_search() и array_key_exists() написаны на C и работают быстрее ваших реализаций на PHP.
Для многократного поиска — сортируйте один раз. Если вы ищете много элементов в одном массиве, отсортируйте его один раз и используйте бинарный поиск.
Используйте ассоциативные массивы как хэш-таблицы. Если ключи уникальны, поиск по ключу происходит мгновенно (O(1)).
Документируйте свои функции. Всегда указывайте, требует ли функция отсортированный массив. Это убережёт других разработчиков (и вас самих) от ошибок.
Тестируйте граничные случаи:
- Пустой массив
- Массив из одного элемента
- Поиск первого и последнего элемента
- Поиск элемента, которого нет
- Поиск с дубликатами
Используйте строгие типы (PHP 7+). Указывайте типы параметров и возвращаемых значений — это помогает избежать ошибок и делает код самодокументированным.

Совет профессионала: В реальных проектах редко приходится писать алгоритмы поиска с нуля. Чаще используются базы данных (SQL) с их мощными индексами, или специализированные библиотеки. Но понимание алгоритмов необходимо для того, чтобы правильно выбирать инструменты и оптимизировать производительность.

Вопросы для самопроверки

Вопрос: В чём основное отличие линейного поиска от бинарного?

Ответ: Линейный поиск проверяет элементы по порядку, работает с любыми данными, сложность O(n). Бинарный поиск делит массив пополам, работает только с отсортированными данными, сложность O(log n).
Вопрос: Сколько сравнений потребуется бинарному поиску в массиве из 1024 элементов в худшем случае?

Ответ: 10 сравнений (2^10 = 1024). В худшем случае бинарный поиск делает log₂(n) сравнений.
Вопрос: Почему нельзя использовать бинарный поиск для неотсортированного массива?

Ответ: Бинарный поиск основан на предположении, что массив отсортирован. Если это не так, алгоритм может пропустить искомый элемент, так как он «отбрасывает» половину массива на каждом шаге.
Вопрос: Что вернёт array_search(), если искомый элемент находится на нулевой позиции?

Ответ: Вернёт 0 (целое число). Поэтому проверять результат нужно строго: if ($result !== false).
Вопрос: Какой алгоритм поиска использует функция in_array() в PHP?

Ответ: Линейный поиск. Она проходит по всем элементам массива, пока не найдёт совпадение.
Вопрос: В каком случае линейный поиск может быть быстрее бинарного?

Ответ: Если искомый элемент находится в самом начале массива. Линейный поиск найдёт его за 1-2 сравнения, а бинарному потребуется около log₂(n) сравнений. Также линейный поиск быстрее на очень маленьких массивах (до 10-20 элементов).
Вопрос: Что такое «О-большое» и почему это важно?

Ответ: «О-большое» (Big O notation) — это способ описания сложности алгоритма. Показывает, как время выполнения растёт с увеличением входных данных. O(1) — константное время, O(n) — линейное, O(log n) — логарифмическое. Это важно для выбора эффективного алгоритма.
Вопрос: Как найти элемент в ассоциативном массиве по ключу максимально быстро?

Ответ: Использовать array_key_exists() или isset(). Они работают за O(1), так как ассоциативные массивы в PHP реализованы как хэш-таблицы.
Вопрос: Что произойдёт, если передать пустой массив в функцию бинарного поиска?

Ответ: Функция должна корректно обработать этот

← Anterior Algoritmos de ordenação em PHP: um guia completo Próximo → Padrões de projeto em PHP: um guia completo