БЕСПЛАТНОЕ РЕШЕНИЕ ЗАДАЧ

Алгоритмы поиска

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

ЛИНЕЙНЫЙ ПОИСК

Простейший алгоритм поиска - линейный. Эталонный массив просматривается последователь-но от первого до последнего элемента.

Наихудший случай - слова нет в массиве (не найдено) – вывод можно сделать после просмотра всего массива.

Достоинство – простота реализации. Недостаток – большое время.

Если используется for всегда выполняется ровно n операций сравнения, независимо от того, найдено слово или нет. Разумно прекращать поиск если, слово найдено (если не требуется найти все вхождения слова).

При равномерном распределении элементов в массиве среднее время поиска обычно пропор-ционально величине n/2.

Во всех ниже изложенных алгоритмах будем считать, что производится поиск в массиве A из N целых чисел элемента, равного X.

Различают первое вхождение элемента в список, последнее вхождение, все вхождения.

ПОИСК С БАРЬЕРОМ

Идея поиска с барьером : не проверять каждый раз в цикле условие достижения границы мас-сива.

Это обеспечивают, установив в массиве: любой элемент, который удовлетворяет условию по-иска. Тем самым будет ограничено изменение индекса. В качестве баръера можно установить искомый элемент добавив его в конец массива.

Достоинство: на одну проверку меньше в цикле.

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

Вычислительная сложность поиска с барьером меньше, чем у линейного поиска, но имеет тот же порядок.

Существует два способа установки барьера: дополнительный элемент или вместо крайнего элемента массива.

ДВОИЧНЫЙ (БИНАРНЫЙ) ПОИСК

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

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

Идея алгоритма: массив каждый раз делится пополам и выбирается та часть, где может нахо-диться нужный элемент. Деление продолжается пока подмассив больше одного элемента, после чего остается проверить этот оставшийся элемент на выполнение условия поиска.

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

В алгоритме двоичного поиска размер фрагмента, где этот поиск должен продолжаться, каж-дый раз уменьшается примерно в два раза. Это обеспечивает вычислительную сложность алго-ритма порядка логарифма N по основанию 2, где N - количество элементов массива.

ИНТЕРПОЛЯЦИОННЫЙ ПОИСК

Предполагается, что массив упорядочен по величинам ключей элементов.

Идея алгоритма: предполагается равномерное распределение величин в некотором их диапазо-не от u до l. Поэтому, зная величину Х ключа поиска, можно предсказать более точное положе-ние искомой записи, чем просто в середине некоторого отрезка файла. Интерполяционный по-иск ассимптотически предпочтительнее бинарного.

Алгоритм основан на формуле i=l+trunc((u-l)*(X-K[l])/(K[u]-K[l]))

Время t работы алгоритма оценивается формулой: t=a*logN

ПОИСК минимума и максимума

При поиске минимума или максимума используют дополнительную переменная min (или max):

1) промежуточной переменной присваивается значение первого числа из последовательности, т.е. принимается, что первое число является текущим минимумом (максимумом);

2) начиная со второго числа, производится сравнение этого числа со значением переменной min (или max) и если число из массива меньше min (больше max), то на место min (max) записыва-ется это число. Теперь это число будет текущим минимумом (максимумом);

После просмотра всех чисел в переменной min (или max) будет находиться окончательное зна-чение минимума (или максимума).

Онлайн всего: 9
Гостей: 9
Пользователей: 0

STUDLAB Сообщить про опечатку на сайте