Файл: Поиск заданного слова в упорядоченном массиве.pdf

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

Задача поиска слова – это очень часто встречающаяся задача. Например, словарь и поиск слова в нём. Словарь – это упорядоченный массив данных (текстовый).

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

Линейный или последовательный поиск – самый простой из алгоритмов поиска элемента в массиве.

Алгоритм заключается в обходе всех элементов массива, как правило, слева на право, и сравнения их с искомым значением. Если значения элемента и ключа совпадают, то поиск возвращает индекс элемента.

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

Тем не менее, этот метод используется для поиска:

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

Он работает как с неотсортированными массивами, так и отсортированными, но для вторых существуют алгоритмы эффективнее линейного поиска (см. 2.2).

То, что данный алгоритм неэффективен при работе с большими массивами, может компенсировать его простота. Его можно применять к неупорядоченным последовательностям, что является плюсом.

В ходе такого поиска выбирается ключ – некая величина, которая сравнивается по очереди со всеми элементами массива.

Алгоритм недаром называют «последовательным», это название означает, что все элементы просматриваются последовательно – от первого к последнему. Если текущий элемент равен ключу, то поиск считается завершённым. Если все элементы пройдены и никакой из них не равен ключу - выдаётся результат о том, что искомый элемент не найден.

В хорошей ситуации, искомый элемент – ключ, будет первым или в первых рядах. В плохой ситуации – он окажется последнем или вообще не будет найден. Тогда придётся выполнить N сравнений (N равно количеству элементов массива).

Такой принцип работы используют не часто. Этот алгоритм оправдывает себя на небольших и/или неотсортированных последовательностях.

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

Пример программы линейного поиска – рисунок 10.

Рисунок 10 – Линейный поиск Pascal

2.2 Бинарный поиск

В практической деятельности часто приходится работать с упорядоченной по некоторому критерию информацией.

На практике часто приходится иметь дело с информацией, которая упорядочена по некоторому критерию. Например, список фамилий, как правило, упорядочен по алфавиту, массив метеорологических данных – по датам наблюдений. Если информация была изначально упорядочена, то можно сделать предположение, в какой части списка может находится искомое слово (в начале или конце). Например, фамилия Якимова будет в конце списка, а Белов в начале.

В данном случае оптимально применение алгоритма двоичного (бинарного) поиска.

Суть метода: последовательность делится пополам на равные части. Поиск выполняется в одной из частей, которая в дальнейшем так же делится пополам и так до получения результата.

Найдя средний элемент (сделать это, зная число элементов массива, не составит труда), и, сравнив его значение с искомым, можно уверено сказать, где относительно среднего элемента находится искомый элемент.

Поскольку в каждом бинарном поиске сравнения используется половина пространства поиска, мы можем утверждать и легко доказать, что бинарный поиск никогда не будет использовать больше, чем (в большой записи) O (log N ) сравнений, чтобы найти целевое значение.

Логарифм – ужасно медленно растущая функция. Если вы не знаете, насколько эффективен бинарный поиск, попробуйте найти имя в телефонной книге, содержащей миллион имен. Бинарный поиск позволяет систематически находить любое имя, используя не более 21 сравнения. Если бы было необходимо управлять списком, содержащим всех людей в мире, отсортированных по имени, можно было бы найти любого человека менее чем за 35 шагов.

Такой поиск предполагает, что у нас есть произвольный доступ к последовательности. Попытка использовать двоичный поиск в контейнере, таком как связанный список, не имеет смысла, и вместо этого лучше использовать простой линейный поиск.

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

Например, есть задача: ряд работников должны изучить ряд картотек. Шкафы не все одинакового размера, и известно для каждого шкафа, сколько папок он содержит. Необходимо найти такое назначение, чтобы каждый работник получал последовательную серию шкафов для просмотра и сводил к минимуму максимальное количество папок, которые работник должен был бы просмотреть.

После ознакомления с проблемой требуется творческий подход. Допустим, что в распоряжении неограниченное количество работников. Важное замечание заключается в том, что для некоторого числа MAX можно рассчитать минимальное количество работников, необходимое для того, чтобы каждому работнику приходилось проверять не более MAX папок (если это возможно).

Решение: некоторому работнику нужно проверить первый шкаф, поэтому выбирается любой работник. Но, поскольку шкафы должны быть назначены в последовательном порядке (рабочий не может изучить шкафы 1 и 3 без проверки 2), всегда оптимально назначать его ко второму шкафу, если это не приведет к превышению предела, который был введен (MAX). Если это число выходит за предел, делается вывод, что его работа выполнена, и назначается новый работник во второй кабинет. Действуем аналогичным образом, пока все кабинеты не будут назначены, и утверждаем, что мы использовали минимально возможное количество работников с введенным нами искусственным ограничением. Количество работников обратно пропорционально MAX: чем выше устанавливается лимит, тем меньше работников понадобится.

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

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

На этом завершается первая часть построения решения для бинарного поиска. Осталось доказать, что условие в основной теореме выполнено. Увеличение x фактически ослабляет ограничение на максимальную рабочую нагрузку, поэтому может потребоваться только такое же количество рабочих или меньше, а не больше. Таким образом, если предикат говорит «да» для некоторого x, он также скажет «да» для всех больших x.

Очень важно правильно выбрать нижнюю и верхнюю границы. Можно заменить верхнюю границу любым достаточно большим целым числом, но нижняя граница не должна быть меньше, чем самый большой шкаф, чтобы избежать ситуации, когда один шкаф будет слишком большим для любого работника, случай, который не будет правильно обрабатываться предикатом. Альтернативой было бы установить нижнюю границу равной нулю, а затем обрабатывать слишком малые x как особый случай в предикате.

Общая сложность решения составляет O ( n log SIZE ), где SIZE - размер пространства поиска. Это очень быстро.

При работе с таким поиском важно учесть:

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

Алгоритм представлен на рисунке 11.

Рисунок 11 – Алгоритм поиска

На рисунке ниже – рисунок 12, представлен конкретный целочисленный массив, и пошаговое выполнение алгоритма бинарного поиска применительно к его элементам. Для экономии места в таблице left, right и mid заменены на a, b и c.

Рисунок 12 – Пример выполнения алгоритма поиска

На данном рисунке изображена последовательность целых чисел, расположенных в порядке возрастания. В качестве ключа выбрано число 16.

Изначально граничными элементами являются элементы с номерами 1 и 9, и значениями 1 и 81.

Вычисляется номер среднего элемента, для чего, как правило, используется формула (right+left)/2, либо left+(right-left)/2 (вторая формула наиболее устойчивая к переполнениям).

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

Алгоритм продолжает выполняться подобным образом, до нахождения на 4 шаге искомого элемента.

Код программы представлен на рисунке 13.

Рисунок 13 – Код бинарного поиска на Pascal

В случае, когда первое значение mid совпадает с ключом, тогда считается, что алгоритм выполнился за свое лучшее время O(1). В среднем и худшем случае время работы алгоритма составляет O(logn), что значительно быстрее, чем у линейного поиска, требующего линейного времени.

ЗАКЛЮЧЕНИЕ

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

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