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

Давайте поговорим предметно о том, что такое структуры данных, алгоритмы и для чего они собственно нужны? Структуры данных позволяют организовывать данные в памяти компьютера или на диске. В одной из предыдущих конспектов я уже описывал о такую примитивную и распространенную структуру данных как массив. Настоятельно рекомендую ознакомиться с данным конспектом перед чтением текущего. Запись вы можете найти в архиве конспектов или просто перейдя по ссылке

Если вы хотите ознакомиться с данным материалом в видео формате, вы можете найти запись в лектории или просто перейти по ссылке. Также вы сможете получить методичку и перезентацию на данную тему под видео - лекцией.

На самом деле массив это не единственная структура данных. Существует множество других структур, таких как хеш таблицы, деревья, стеки и многие другие. В рамках
данной лекции мы рассмотрим пример алгоритма поиска на такой структуре данных как массив.

Выполнение различного рода операций над структурами данных называется алгоритмом. В ряд таких операций как правило входит поиск, удаление, вставка, сортировка и т.д.

Как правило изучение алгоритмов в рамках такой операции как “поиск” начинается с понимания как работает линейный поиск.

search_320x240.jpg

Значение слова “поиск” вполне очевидно, но что такое поиск данных в информатике? Поиск данных - раздел информатики, изучающий алгоритмы для поиска и обработки информации как в структурированных (например БД) так и неструктурированных (например файл) данных.

Существует ряд алгоритмов или иначе говоря разновидностей поиска, например линейный и двоичный поиск

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

Представьте, что у вас есть структура данных массив состоящая из 10 элементов. Значения этих элементов - это список имен пользователей.

$collection = [
    'John',
    'Kate',
    'Megan',
    'Karl',
    'David',
    'Stephan',
    'Alex',
    'Alisan',
    'Alisa',
    'Arnold',
];

Предположим, что нам необходимо найти пользователя с именем “Kate”. То есть академически говоря нам необходимо применить какой - либо алгоритм поиска над структурой данных массив с целью обнаружения искомого значения в наборе данных.

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

В примере выше у нас есть массив состоящий из 10 элементов, не такой и большой объем верно? Если учесть тот факт, что максимальный порог структуры ограничен десятками или возможно сотнями элементов, то вполне можно применить алгоритм “линейный поиск”.

Линейным поиском называют последовательный поиск. Иначе говоря в рамках этого поиска мы начинаем перебирать каждый элемент массива и сравнивать его значение с искомым пока не найдем его.

Linear-Search_2_compress.png

Давайте рассмотрим пример реализации линейного поиска

function linear_search(string $needle, array $collection) : bool
{
    $num = 1;

    foreach ($collection as $item) {
        echo 'step ' . $num++ . "\n";
        if ($item === $needle) {
            return true;
        }
    }

    return false;
}

Как видим у нас есть функция linear_search которая имеет 2 параметра. Первый параметр это искомое значение, второй это структура данных в которой нужно поискать элемент или иначе говоря применить алгоритм поиска. Тело данной функции инкапсулирует алгоритм линейный поиск. При помощи цикла foreach производится последовательный перебор элементов массива и каждое значение этого элемента сравнивается с искомым значением. Если значение было найдено, цикл прерывается и функция возвращает истинный результат, в противном случае - ложный.

Запустим нашу программу

php ex1.php "Kate"
step 1
step 2
found

Как видим, искомое имя “Kate” было найдено за 2 шага алгоритма, так как имя было расположено во втором элементе массива.

Теперь давайте поговорим об эффективности данного алгоритма. Забегая вперед должен сказать, что алгоритм эффективен только в тех случаях когда объем структуры данных (в нашем случае массив) не велик. Если искомый элемент находится в начале массива, алгоритм покажет себя с лучшей стороны, иначе говоря искомое значение будет обнаружено за наименьшее количество шагов, а значит время поиска будет невелико, но если искомое значение будет располагаться ближе к концу массива, алгоритм должен пробежаться по всем элементам, а значит количество шагов может быть не малым, поэтому и время выполнения тоже будет расти.

Все вышесказанное можно отразить единой формулой:

N/2

где N - количество сравнений (шаги), а 2 означает, что в среднем необходимо произвести ровно половину сравнений от общего объема массива. Почему половину? В лучшем случае искомый элемент может располагаться в начале массива, в худшем - в конце или элемента в структуре может вообще не быть. Среднее арифметическое - это половина.

Разумно будет сказать, что если искомого значения в массиве не существует, то алгоритм перебирает все элементы данного массива прежде чем выдать отрицательный результат, то есть количество шагов будет равняться размеру массива.

php ex1.php "Jeck"
step 1
step 2
step 3
step 4
step 5
step 6
step 7
step 8
step 9
step 10
not found

Если предположить, что количество элементов в структуре 1 млн или более, то сложно назвать алгоритм “линейный поиск” подходящим, так как его эффективность маловероятно будет высокой. Поэтому в зависимости от задачи и ее условий может применяться свой наиболее рациональный для конкретного случая алгоритм. Например для поиска элемента в большом наборе данных можно применить алгоритм “двоичный поиск”.

Необходимо также отметить, что все ранее сказанное относительно эффективности применимо к структуре, в которой хранятся только уникальные значения. Но имена могут и повторяться, не правда ли? В структуре данных могут располагаться например два человека с именем Karl, тогда эффективность алгоритма линейный поиск сразу же падает. Почему? Потому что алгоритму уже необходимо произвести не N/2 шагов при поиске, а все N, так как найдя нужное значение цикл не должен прерываться и обязан дойти до конца.

При выборе подходящего алгоритма должны быть учтен такой важный момент как возможность или невозможность хранения дубликатов в структуре данных.

Информация

Автор конспекта


Дата создания: 03.01.2019
Категория: Алгоритмы и структуры данных