Массивы наиболее часто используются при подготовке статистических сводок, справочных изданий, словарей и т.д. Самый простой способ поиска информации в данном случае - последовательный просмотр-перебор всех элементов массива. Для облегчения поиска необходимых данных содержимое массива упорядочивается, как правило уже известными вам способами. Рассмотрим наиболее часто встречающуюся задачу поиска необходимого элемента в отсортированном массиве, и алгоритм её решения. Дан отсортированный по возрастанию массив вещественных чисел A состоящий из n элементов. Определить, содержит ли данный массив число B, и если содержит, то определить номер (индекс) данного элемента в массиве. Предположим, что в массиве A имеется элемент, равный B, т.е. существует такой индекс p, что A[p]=B. По результату любого сравнения A[s]<B (1<s<n) мы сразу определяем, лежит ли p в диапазоне от 1 до s, или же в диапазоне от s+1 до n: второе будет иметь место, если неравенство A[s]<B справедливо, а первое - если не справедливо. Это свойство данного сравнения используется в алгоритме деления пополам.

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

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

Сказанное можно записать в виде последовательности операторов TP. В этом фрагменте p и q обозначают упомянутые верхнюю и нижнюю границы.

     p:=1; q:=n;
     while p<q do
       begin
        s:=(p+q) div 2;
        if a[s]<b then p:=s+1
                  else q:=s;
       end;

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

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

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

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

Задания для самостоятельного выполнения.

1. Напишите программу, которая организует хранение в массиве 15 различных введённых с клавиатуры целых чисел. Содержимое массива сортируется по возрастанию. После этого, с клавиатуры запрашивается контрольное число, наличие которого в массиве необходимо проверить. Номер элемента массива, в положительном случае, выводится на экран монитора.
2. Напишите программу, которая организует хранение в массиве 10 различных целых чисел. Содержимое массива сортируется по возрастанию. После этого, с клавиатуры вводится контрольное число. Наличие которого в массиве необходимо проверить. В положительном случае замените элемент массива, равный контрольному числу, нулём. Содержимое массива выводится на монитор.
3. Напишите программу, которая организует хранение в массиве 15 различных введённых с клавиатуры целых чисел. Содержимое массива сортируется по убыванию. После этого, с клавиатуры запрашивается контрольное число, наличие которого в массиве необходимо проверить. На экран монитора выводится содержимое массива до "контрольного числа" включительно.
4. Дан массив из 10 целых чисел. Отсортируйте его и найдите в нём контрольное число. Все элементы до контрольного числа замените на противоположные.
5. Дан массив из 20 символов. Отсортируйте его и найдите в нём контрольный символ. Выведите на экран содержимое массива начиная с символа равного контрольному символу.
6. Дан массив, состоящий из 15 символов. Содержимое массива сортируется по убыванию. После этого вводится контрольное целое число в диапазоне от 0-255. Необходимо определить наличие в массиве символа, имеющего номер "контрольное число". В положительном случае сам символ и его индекс в массиве выводятся на экран.
7. Дан массив, состоящий из 15 целых чисел, в диапазоне от 0 до 255. Содержимое массива сортируется по возрастанию. После этого вводится контрольный символ. Необходимо определить наличие в массиве числа, равного номеру контрольного символа. В положительном случае число и его индекс в массиве выводятся на экран.
8. Дан массив А состоящий из 10 символов. Отсортируйте его по возрастанию. Организуйте массив целых чисел Б, заполнив его номерами символов из массива А. Введите контрольное число в диапазоне от 0 до 255 и определите его наличие в массиве Б. В положительном случае выведите на экран найденное число и его индекс в массиве.
9. Дан массив Б состоящий из 10 чисел в диапазоне от 0 до 255. Отсортируйте его по возрастанию. Организуйте символьный массив А, заполнив его символами с номерами элементов массива Б. Введите контрольный сивол и определите его наличие в массиве А. В положительном случае выведите на экран сам символ и его индекс в массиве.
10. Дан массив А состоящий из 20 целых чисел. Отсортируйте его по убыванию. Введите с клавиатуры 2 контрольных числа a и b. Определите наличие в массиве чисел, лежащих в диапазоне от a до b. В положительном случае выведите найденные числа и их индексы в массиве на экран.
11. Дан массив Б состоящий из 20 символов. Отсортируйте его по возрастанию. Введите с клавиатуры 2 контрольных символа a и b. Определите наличие в массиве символов лежащих в диапазоне от a до b. В положительном случае выведите найденные символы и их индексы на экран.
12. Дан массив А состоящий из 20 целых чисел. Отсортируйте первую половину массива по возрастанию, а вторую по убыванию. Введите контрольное число и определите его наличие в массиве А. В положительном случае выведите найденное число и его индекс на экран.

НАЗАД                    ДАЛЕЕ