←  Целочисленная арифметика

олимпиадники-информатики

»

Бинарный поиск

yanush фотография yanush 22 дек 2011

Двоичный (бинарный) поиск (также известен как метод деления пополам)
Смысл этого поиска в том, чтобы в массиве отсортированном по возрастанию найти номер числа x. Этот поиск гораздо быстрее простого перебора.
Он работает следующим образом:


var n, x, l, r, f, m, i: longint;
a : array[1..1000] of longint;
begin
readln(n, x); {ввод кол-ва чисел и число  котороe требуется найти}
for i := 1 to n do
   	read(a[i]);
l := 1; {левый показатель границы поиска}
r := n; {правый показатель границы поиска}
f := 0; {флажок, если он 0, то мы ещё не нашли число, можно заменить переменной типа boolean}
while (f = 0) and (r >= l) do  {пока мы не нашли число и пока ещё есть где искать мы делаем следующее}
        	begin
        	m := (l + r) div 2; {нашли серединку в области поиска}
        	if a[m] = x then
   				f := 1    	{если мы нашли это число, тогда флажок вверх}
        	else if a[m] > x then r := m - 1  {иначе если это число меньше числа посередине нашей области, то правую границу нам надо сдвинуть к этой серединке, но на 1 число влево}
   				else l := m + 1; {иначе левую границу сдвинуть к серединке, но на число вправо}
        	end;
if (f = 1) then
  	writeln(m)
else
  	writeln('Данного числа в массиве нет'); {вывод}
end.
Ответить