PHP. Изучение алгоритмов. Линейный поиск
В серии статей по алгоритмам поиска я рассматриваю различные виды поиска и их реализации на языке PHP. Алгоритмы поиска в мире PHP разработки не так сильно важны, поскольку уже есть множество реализаций, но базовые вещи и их устройства необходимо знать, чтобы оценивать на сложность свой код и выбирать оптимальные решения.
В первой статье серии алгоритмов поиска на PHP рассматривается самый простой алгоритм поиска - линейный.
Линейный или последовательный — это самый простой поиск, так как предварительной подготовки массива не требуется, а поиск осуществляется путем сравнения каждого элемента с искомым значением. Поиск завершится возвратом индекса элемента, а если он не найден, то вернется -1. Хотя тут спорный момент, что возвращать, в случае, если ничего не нашлось. Оставим это на усмотрение разработчика.
Сложность этого алгоритма составляет O(N). По поводу того, как высчитывается сложность, можно почитать в этой статье. Стоит отметить, что данный поиск показывает наибольшую эффективность только для массивов длиной не более 100 элементов.
Давайте напишем класс, который будет помогать в реализации разных видов поиска.
<?php
declare(strict_types = 1);
class ArraySearch {
/**
* Ищет индекс элемента в массиве.
*
* @param array $array Массив данных
* @param mixed $value Искомое значение
*
* @return int Возвращает индекс найденного элемента или -1, если элемент не был найден
*/
public static function linear(array $array, $value): int {
foreach ($array as $index => $indexValue) {
if ($indexValue === $value) {
return $index;
}
}
return -1;
}
}
Теперь, запустим тест и увидим, что для массива со значениями от 1 до 10 и искомым значением 8, индекс будет равен 7, а для значения 11 индекс будет равен -1.
З.Ы. А еще я веду свой блок в ВК. Если будет интересно, то забегайте.
Максим Епихин
3 года назад