Поиск — обработка некоторого множества данных с целью выявления подмножества данных, соответствующего критериям поиска.
Все алгоритмы поиска делятся на
- поиск в неупорядоченном множестве данных;
- поиск в упорядоченном множестве данных.
Основными алгоритмами поиска являются линейный и бинарный поиск.
Линейный поиск. Данный алгоритм является простейшим алгоритмом поиска и в отличие, например, от двоичного поиска, не накладывает никаких ограничений на функцию и имеет простейшую реализацию. Поиск значения функции осуществляется простым сравнением очередного рассматриваемого значения (как правило поиск происходит слева направо, т.е.от меньших значений аргумента к большим) и, если значения совпадают (с той или иной точностью), то поиск считается завершенным. В связи с малой эффективностью по сравнению с другими алгоритмами линейный поиск обычно используют только, если отрезок поиска содержит очень мало элементов, тем не менее линейный поиск не требует дополнительной памяти или обработки/анализа функции. Также, линейный поиск часто используется в виде линейных алгоритмов поиска максимума/минимума.
Алгоритм последовательного поиска:
Шаг1. Полагаем, что значение переменной цикла i=0.
Шаг2. Если значение элемента массива x[i] равно значению ключа key, то возвращаем значение, равное номеру искомого элемента, и алгоритм завершает работу. В противном случае значение переменной цикла увеличивается на единицу i=i+1.
Шаг3. Если i<k, где k-число элементов массива х, то выполняется шаг2, в противном случае – работа алгоритма завершена и возвращается значение равное -1. При наличии в массиве нескольких элементов со значением key алгоритм находит только первый из них (с наименьшим индексом).
Бинарным поиском можно пользоваться лишь в отсортированном массиве!
Бинарный поиск не используется для поиска максимального или минимального элементов, так как в отсортированном массиве эти элементы содержатся в начале и в конце массива соответственно, в зависимости от тога как отсортирован массив, по возрастанию или по убыванию. Поэтому алгоритм бинарного поиска применим, если необходимо найти некоторый ключевой элемент в массиве. То есть организовать поиск по ключу, где ключ — это определённое значение в массиве.
Идея алгоритма: массив каждый раз делится пополам и выбирается та часть, где может нахо-диться нужный элемент. Деление продолжается пока подмассив больше одного элемента, после чего остается проверить этот оставшийся элемент на выполнение условия поиска.
Существуют две модификации этого алгоритма для поиска первого и последнего вхождения. Все зависит от того, как выбирается средний элемент: округлением в меньшую или большую сторону. В первом случае средний элемент относится к левой части массива, а во втором - к правой.
В алгоритме двоичного поиска размер фрагмента, где этот поиск должен продолжаться, каж-дый раз уменьшается примерно в два раза. Это обеспечивает вычислительную сложность алго-ритма порядка логарифма N по основанию 2, где N - количество элементов массива.
