3.2. Поиск в упорядоченных таблицах
 

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

Поиск в упорядоченных таблицах можно организовать по разному.
Последовательный поиск. Выполняется так же, как и в неупорядоченной таблице, но поиск прекращается, либо когда найдена запись {p_i = q), либо когда ключ очередной записи станет больше заданного ключа (р_i> q), либо по достижении конца таблицы. Последние два события соответствуют отсутствию записи с заданным ключом.
Двоичный (бинарный, логарифмический ) поиск в упорядоченной таблице. Является самым экономичным. Он состоит в последовательном делении таблицы пополам и определении, в какой из двух частей находится искомая запись. Последующему делению каждый раз подвергается часть, содержащая искомый ключ. Поскольку таблица упорядочена по возрастанию ключа, то чтобы определить, в какой части находится требуемое значение ключа, достаточно сравнить значение ключа в точке деления с искомым.

Длина двоичного поиска для п элементов имеет порядок O(log₂n). Например, для таблицы из 1000 элементов средняя длина последовательного просмотра равна 500, в то время как длина двоичного поиска — только 10, а для 1000000 — лишь 20.

Иногда используются частично упорядоченные таблицы. Таблица состоит из разделов, соответствующих различным интервалам ключа. Разделы упорядочены, а внутри разделов записи не упорядочены. Для поиска записей используется комбинированный метод: раздел отыскивается путем двоичного поиска, а внутри раздела применяют последовательный поиск.

Рассмотрим программу с двумя вариантами функции двоичного поиска. Варианты отличаются только местом проверки того, не является ли элемент искомым в точке деления. В первом варианте такая проверка осуществляется в теле цикла, а во втором варианте — в управляющем операторе цикла while.
Пример.
/* БИНАРНЫЙ ПОИСК В УПОРЯДОЧЕННОЙ ТАБЛИЦЕ 7
#include <stdio.h>
#define m 20
int bisearch(int A[],int n,int key);
main()
{ int i.key, A[m];
printf(" \nБинарный поиск в упорядоченной таблице ");
printf("\n Введите %d целых чисел в возрастающем порядке»,m);
for (i=0; iscanf("%d",&A[i]);
printf("\n Введите значение искомого ключа =>");
scanf("%d",&key);
i = bisearch1(A,m,key);
if(i== -1)
printf(" Ключ %d не найден ",key);
else
printf(" %d-u элемент имеет ключ = %d \n",i,A[i]);
getch(); return 0;
}
/* ФУНКЦИЯ БИНАРНОГО ПОИСКА. Вариант 1 */
int bisearch1(int A[],int n,int key)
{int li,rj,k;
li=0; rj=n-1;
while (li ≤ rj )
{ к = (li+rj)/2;
if (key > A[k])
li = k+1;
else
if (key < A[k])
rj = k-1;
else return k;
}
return -1;
}
/* ФУНКЦИЯ БИНАРНОГО ПОИСКА Вариант 2 */
int bisearch2(int A[],int n.int key)
{ int li,rj,k;
li=0; rj=n-1; к = li;
while ( li ≤ rj && A[k] != key )
{ к = (li+rj)/2;
if (key > A[k])
li = k+1;
else
if (key < A[k])
rj = k-1;
}
return (A[k] == key) ? к : -1;