Алгоритмы поиска
Примеры поиска : поиск требуемого элемента в базе данных (телефонный справочник); поиск вхождения одного фрагмента текста в другой (сравнение двух текстов, антиреферат, поиск плагиата) и т.д. Результат поиска как правило булевский, или указание места расположения элемента.
ЛИНЕЙНЫЙ ПОИСК
Простейший алгоритм поиска - линейный. Эталонный массив просматривается последователь-но от первого до последнего элемента.
Наихудший случай - слова нет в массиве (не найдено) – вывод можно сделать после просмотра всего массива.
Достоинство – простота реализации. Недостаток – большое время.
Если используется 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) будет находиться окончательное зна-чение минимума (или максимума).
ЛИНЕЙНЫЙ ПОИСК
Простейший алгоритм поиска - линейный. Эталонный массив просматривается последователь-но от первого до последнего элемента.
Наихудший случай - слова нет в массиве (не найдено) – вывод можно сделать после просмотра всего массива.
Достоинство – простота реализации. Недостаток – большое время.
Если используется 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) будет находиться окончательное зна-чение минимума (или максимума).
