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


- - - - -

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


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

#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 анононимных