Поиск
Алгоритмические и математические аспекты поиска достаточно сложны и их исследованию посвящены многочисленные работы. Наиболее полно эти вопросы рассматриваются в ранее упоминавшейся трилогии Д. Кнута. Мы же ограничимся самыми простыми алгоритмами и программами, позволяющими понять суть проблемы и познакомиться с некоторыми подходами к повышению эффективности поиска.
В достаточно общих чертах задача поиска формулируется следующим образом. Имеется массив а, содержащий п однородных объектов (чисел, строк, записей), и нужно установить, содержится ли в нем заданный объект q. При положительном ответе следует дополнительно сообщить порядковый номер (индекс) j найденного объекта (a[j] = q).
Последовательный поиск
Если исходный массив а не упорядочен, то единственно разумным способом является последовательный перебор всех элементов массива и сравнение их с заданным значением. В лучшем случае мы можем получить ответ на первом же шаге, если q = а [ 1 ]. В худшем случае придется перебрать все п элементов и только после этого дать положительный или отрицательный ответ. В среднем количество проверок может оказаться порядка п/2.
Классический алгоритм последовательного поиска включает следующие шаги:
Большинству программистов кажется, что приведенный алгоритм является оптимальным и ничего сократить в нем нельзя. Однако это — очень распространенное заблуждение. Д. Кнут приводит модификацию алгоритма последовательного поиска, в которой цикл содержит не две логические проверки (шаги S2 и S4), а всего одну. В нашем случае это довольно существенно, т. к. описанный выше цикл реализуется пятью-шестью машинными командами и исключение из него даже одной команды эквивалентно повышению производительности на 15—20%.
Модификация состоит в том, что к массиву а добавляется еще один элемент, в который до начала цикла заносится q. Теперь цикл повторяется до тех пор, пока не будет встречен элемент а [ j ], равный q, и необходимость в проверке j < n + 1 отпадает. Конечно, перед возвратом из процедуры надо удостовериться в том, что найденный индекс j не равен n + l. Но такая проверка выполняется за пределами цикла.
Для программистов, имеющих дело с языком ассемблера, известен и более простой прием, не требующий расширения исходного массива. Очевидно, цикл поиска можно организовать как в прямом (j меняется от 1 до n), так и в обратном (j меняется от n до i) направлении. Обратный цикл на ассемблере реализуется с помощью команды LOOP, организующей возврат в начало цикла с одновременным вычитанием 1 из счетчика сх. Цикл повторяется до тех пор, пока содержимое регистра сх не станет равным 0. Таким образом, дополнительного сравнения (j < n + 1) здесь не требуется.
В приводимых ниже программах последовательного поиска возвращаемое соответствующей функцией значение либо равно индексу найденного элемента, либо равно — 1, если искомая величина в массиве не обнаружена.
Функция ssearch.bas
FUNCTION SSEARCH(Q,A(),N)
FOR J=0 TO N-l
IF Q=A(J) THEN SSEARCH=J: EXIT FUNCTION
NEXT J
SSEARCH=-1
END FUNCTION
Функция ssearch.c
int ssearch(int q, int *a, int n)
}
register int j;
for(j=0; j<n; j++)
if(q==a[j]) return j;
return -1;
}
Функция ssearch.pas
function ssearch(q:integer;a:array of integer;n:integer):integer;
var
j:integer; begin
for j:=0 to n-1 do
if q=a[j] then
begin
ssearch:=j;
exit;
end;
ssearch:=-l;
end;
Бинарный поиск
Бинарный поиск, суть которого была раскрыта выше на примере поимки льва в пустыне, применяется только для предварительно упорядоченных массивов. Несмотря на абсолютную прозрачность идеи деления пополам, ее программная реализация требует большой аккуратности как в использовании сравнений, так и в выборе очередного интервала поиска.
Исключим тривиальный случай, когда искомое значение g выходит за пределы интервала [а[1],а[n]]. Обозначим через left и right индексы элементов массива, определяющие текущий диапазон поиска. В начальный момент left = 1 и right = n. Сравним значение q с величиной среднего элемента a [mid] в диапазоне поиска (mid = (left + right)/2). Если значение q строго меньше a [mid], то заменим правую границу диапазона поиска на mid - 1. Если значение q строго больше a [mid], то заменим левую границу диапазона поиска на mid + 1. Если оба строгие неравенства не выполнены, то имеет место равенство q = a [mid], и в этом случае процедура поиска завершена успешно.
Поиск следует продолжать до тех пор, пока значение индекса left не превосходит значения индекса right. А нарушиться это условие может только в случае, когда диапазон поиска сведен к минимальному (right = left + l) и имеют место неравенства:
a[left] < q < a[right]
Это означает, что значение q в массиве а не содержится.
Функция bsearch.bas
FUNCTION BSEARCH(Q,A() ,N) LEFT=0: RIGHT=N-1
WHILE LEFT <= RIGHT
MIDDLE=(LEFT+RIGHT)\2
IF Q < A(MIDDLE) THEN RIGHT=MIDDLE-1: GOTO M
IF Q > A(MIDDLE) THEN LEFT=MIDDLE+1: GOTO M
BSERACH=MIDDLE : EXIT FUNCTION M:WEND
BSEARCH=-1 END FUNCTION
Функция bsearch.c
int bsearch(int q,int *a,int n)
{
register int left,right,mid;
left=0; right=n-l;
for(;left <= right;)
{
mid=(left+right)12;
if(q < a[mid]) right=mid-l;
else if(q > a[mid]) left=mid+l;
else
return mid; }
return -1; }
Функция bsearch.pas
function bsearch(q:integer;a:array of integer;n:integer):integer;
var
left,right,mid:integer;
begin
left:=0; right:=n-l;
until left <= right do
begin
mid:=(left+right) div 2;
if q < a[mid] then right=mid-l
else if q > a[mid] then left=mid+l
else
begin
bsearch:=mid;
exit;
end;
end;
bsearch:=-l;
end;
Идея бинарного поиска может быть с успехом реализована в игре с отгадыванием задуманного целого числа из заранее установленного диапазона [O,N]. В ответ на число, предложенное угадывающим, его партнер может дать один из трех ответов:
Оптимальное поведение отгадывающего в точности повторяет схему бинарного поиска. Сначала надо предложить число, расположенное в середине интервала, т. е. N/2. Затем, сузив интервал поиска вдвое, повторить аналогичный маневр. Попадание в цель произойдет не более чем через log2N шагов.
Приведенные ниже тексты программ реализуют оптимальную тактику отгадывания чисел из диапазона [0,100], затрачивая на это не более 7 шагов. На вопросы программы загадавший должен нажимать клавишу Y или у (в случае положительного ответа) или любую другую клавишу, если вопрос программы не соответствует загаданному числу.
Программа 4_02.bas
'Программа угадывания задуманного числа в интервале [0,100]
DEFINT A-Z
CLS
LEFT=0: RIGHT=100:
DO
MIDDLE=(LEFT+RIGHT)\2
PRINT "Задуманное Вами число больше, чем"; MIDDLE; " (Y/N) - ";
INPUT "",A$
IF RIGHT-LEFT <= 1 THEN
IF A$="Y" OR A$="y" THEN
PRINT "Вы задумали ";RIGHT: END
ELSE
PRINT "Вы задумали ";LEFT: END
END IF
END IF
IF A$="Y" OR A$="y" THEN LEFT=MIDDLE+1 ELSE RIGHT=MIDDLE
LOOP
END
Программа 4_02.с
/* Программа угадывания задуманного числа в интервале [0,100] */
#include <stdio.h>
#include <conio.h>
main ()
{
int left=0, right=100, middle, ok;
char ch;
clrscr();
for (;;)
{
middle={left+right)/2;
printf("\n Задуманное Вами число больше, чем % d (Y/N) - ", middle);
ch=getche();
if(right-left <= 1)
if (ch=='Y' || ch == 'y') { ok=right; break; }
else { ok=left; break;}
if(ch=='Y' II ch== 'y') left=middle+l;
else right=middle; }
printf("\пВы задумали %d",ok); getch(); }
Программа 4_02.pas
{ Программа угадывания задуманного числа в интервале [0,100] }
uses Crt;
var
ch: char;
left, right, middle, ok: byte;
begin
left:=0;
right:=100;
clrscr;
repeat
middle := (left + right) div 2;
write('Задуманное Вами число больше, чем ',middle,' (Y/N) - ');
ch:=readkey;
writeln(ch);
if (right-left <= 1) then
if (ch='Y') or (ch = 'y') then begin ok:=right;
break;
end else begin ok:=left;
break;
end; if(ch='Y') or (ch='y') then left := middle + 1
else right := middle;
until false;
writeln('Вы задумали ',ok);
readln;
end.
