Перейти к содержимому


- - - - -

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


В этой теме нет ответов

#1 yanush

    Пользователь

  • Пользователи
  • PipPip
  • 21 сообщений

Отправлено 22 декабря 2011 - 11:38

Двоичный (бинарный) поиск (также известен как метод деления пополам)
Смысл этого поиска в том, чтобы в массиве отсортированном по возрастанию найти номер числа 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.






Количество пользователей, читающих эту тему: 1

0 пользователей, 1 гостей, 0 анононимных