Практика программирования (Бейсик, Си, Паскаль)
Поиск - часть 3
Исключим тривиальный случай, когда искомое значение 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]. В ответ на число, предложенное угадывающим, его партнер может дать один из трех ответов:
