Поиск элемента в упорядоченном массиве

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

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

Дан отсортированный по возрастанию массив вещественных чисел А, состоящий из N элементов. Определить, содержит ли данный массив число В, и если содержит, то определить номер (индекс) данного элемента в массиве.

Предположим, что в массиве А имеется элемент, равный В, т.е. существует такой индекс р, что А[р]=В. По результату любого сравнения А[s]<b (1<s<N) мы сразу определяем, лежит ли р в диапазоне от 1 до s, или же в диапазоне от s+1 до N: второе будет иметь место, если неравенство A[s]<B справедливо, а первое — если не справедливо. Это свойство данного сравнения используется в алгоритме деления пополам.

Алгоритм деления пополам

Первоначально номера крайних элементов массива 1 и N берут в качестве границ поиска элемента; далее, до тех пор, пока границы не совпадут, шаг за шагом сдвигают эти границы следующим образом: сравнить В с А[s], где s — целая часть среднего арифметического границ; если A[s]<B, то заменить прежнюю нижнюю границу на s+1, оставив верхнюю границу без изменения, иначе оставить без изменения нижнюю границу, а верхнюю границу заменить на s. Поиск закончится, когда границы совпадут.

Сказанное выше демонстрирует фрагмент программы, приведенный ниже.

Схематически процесс поиска можно изобразить в виде схемы:

Заметим сразу следующее: мы исходим из предположения, что среди элементов массива имеется такой, который равен В. Если заранее неизвестно, имеется или нет такой элемент, то, получив р, надо дополнительно проверить, действительно ли A[p]=B.

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

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

1.  В чем заключается идея поиска элемента методом деления пополам?

2.  Опишите последовательность действий при создании алгоритма для поиска элемента в массиве методом деления пополам.