Поиск может быть выполнен более эффективно, если элементы таблицы упорядочены (отсортированы) согласно некоторому естественному порядку аргументов.
Эффективным методом поиска в упорядоченном списке из n элементов является так называемый бинарный или логарифмический поиск. Символ S, который следует найти, сравнивается с аргументом элемента (n+1)/2 в середине таблицы. Если этот элемент не является требуемым, мы должны просмотреть только блок элементов, пронумерованных от 1 до (n+1)/2-1, или блок элементов от (n+1)/2+1 до n в зависимости от того, меньше искомый элемент S или больше элемента, с которым его сравнивали.
Затем мы повторяем процесс над блоком меньшего размера. Так как на каждом шаге число элементов, которые будут содержать S, сокращается наполовину, максимальное число сравнений равно 1+log2n [1].
Алгоритм бинарного поиска на языке С представлен на рис 5.15.
int Find(int len, char **table, char *id)
{
int end=len, begin=0, middle;
for(int i=0;i<len;i++)
{
middle=(end-begin)/2;
if(strcmp(table[i],id)= =0) return i;
if(strcmp(table[i],id)>0) end = middle;
if(strcmp(table[i],id)<0) begin = middle;
}
return –1;
}
Рис 5.15.Алгоритм бинарного поиска