Практика программирования (Бейсик, Си, Паскаль)



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




Содержание  Назад  Вперед