Лабораторная работа №4

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

Цель работы:

Исследовать один из наиболее распространенных методов поиска данных– бинарный (двоичный) поиск.

Общие сведения

Пусть

–целочисленный массив и

; b – целое число. Рассмотрим задачу: выяснить, входит ли данное число в массив

и если входит, то каково значение p, для которого ap = b? Эту задачу мы назовем задачей поиска элемента.

Областью поиска служит n-элементный ряд, предварительно отсортированный. Вначале диапазон поиска определяется граничными значениями Low = 1 и High = n. Строим первую «гипотезу», полагая, что искомое значение находится в позиции Test – где-то посередине между границами Low и High. Если проверка подтверждает это, то поиск успешно завершен. Если значение в позиции Test меньше искомого, нижней границей (Low) становится Test + 1, а если больше, то модифицируется верхняя (High) граница – для нее принимается значение, равное Test – 1. Описанный процесс постепенного сближения границ поиска с последующей проверкой среднего элемента повторяется многократно, завершаясь одним из двух исходов: либо нужное значение обнаруживается (успех), либо Low становится больше High (неудача).

Максимальное количество проверок, необходимое для завершения бинарного поиска (при любом исходе – удачном или неудачном), определяется по формуле , где ceil обозначает функцию, возвращающую ближайшее целое число, большее или равное ее аргументу. Другими словами, k есть наименьшее целое, такое, что 2k равно или больше, чем n + 1. Например, если n = 100, для сортировки потребуется не более семи проверок, поскольку 27 = 128.

Пример

Пусть b = 6, а массив а состоит из 10 элементов: 3 5 6 8 12 15 17 18 20 25.

Шаг 1. Найдем номер среднего элемента:

(Low=1, High=10). Так как 6

Шаг 2. Рассматриваем лишь первые 4 элемента массива; находим индекс среднего элемента этой части

(Low=1, High=4). 6>a[2], следовательно, первый и второй элементы из рассмотрения исключаем: 3 5 6 8 12 15 17 18 20 25.

Шаг 3. Рассматриваем два элемента; значение

(Low=3, High=4): 3 5 6 8 12 15 17 18 20 25. a[3] = 6! Элемент найден, его номер – 3.

Контрольные вопросы

1. Как в Паскале разделить нацело два числа?

2. Есть ли в Паскале аналог функции ceil?

3. За сколько шагов наверняка завершится поиск элемента в массиве из 1000 элементов?

4. Когда число элементов ряда удваивается, на сколько увеличивается максимально необходимое количество проверок?

Варианты заданий

Для всех вариантов предварительно написать процедуру поиска

1. Опишите массив записей, содержащих фамилию абонента и номер его телефона. Запрограммируйте двоичный поиск в телефонном справочнике.

2. Индексом называется таблица, содержащая отсортированные значения некоторых ключей и их местоположение в массиве записей. Индексом пользуются для ускорения поиска в массиве (сам массив может быть неотсортирован). Запрограммируйте процедуру составления индекса и

2.1. Последовательного поиска при помощи индекса.

2.2. Бинарного поиска при помощи индекса.

3. Пусть задан в виде последовательности символов некоторый текст T, состоящий из слов и есть два списка из нескольких слов в виде двух массивов A и B. Написать программу, преобразующую текст T в текст S, путем замены каждого вхождения слова A[i] на соответствующее слово B[i].

4. В нашем примере поиск проводился в массиве, упорядоченном по возрастанию. Напишите процедуру бинарного поиска в массиве, упорядоченном по убыванию.

5. Дан массив из строк (например, фамилий). Отсортировать его по алфавиту и написать процедуру вставки новой фамилии после заданной так, чтобы алфавитный порядок не нарушился. Предусмотреть ситуацию, когда массив заполнен «до отказа» и вставка нового элемента невозможна.

6. Имеется железнодорожное расписание, содержащее номер рейса поезда, времена отправления и прибытия и станцию прибытия. Организовать поиск номера поезда, время отправления и прибытия, если задана станция.

7. Компания с целью определения спроса на свою продукцию организует некоторый опрос. Продукция – компакт-диски с записями шлягеров. Все опрашиваемые делятся на две группы в соответствии с полом. Каждый опрашиваемый должен назвать три песни, которые идентифицируются номерами от 1 до N (пусть N = 10). Файл с данными обрабатывается программой, которая должна печатать:

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

7.2. Три наиболее популярные песни (хиты) и два списка (в соответствии с группами) с именами всех тех ответивших, которые поставили на первое место один из этих трех хитов.

Назад На главную

Учебник по языку Pascal Лабораторные работы по программированию Справочник

Нет комментариев.

Оставить комментарий: