Песни о Паскале — страница 57 из 112

      Break;       { выход из цикла }
      end
end;

Новая функция сравнивает искомое число с элементами массива, перебирая их последовательно до тех пор, пока не найдет подходящий элемент или не уткнется в конец массива. В случае успеха она вернет индекс элемента в массиве, а иначе – минус единицу.

Этот способ называют поиском прямым перебором или линейным поиском. Линейный поиск прост, но крайне медлителен. Если бы библиотекарь искал заказанную книгу прямым перебором, клиент дремал бы в ожидании заказа месяцами! Но библиотекарь справляется с поиском, живо находя нужное среди сотен тысяч томов. Как ему удается это?

Все дело в порядке. Там, где порядок, искать проще и быстрей. Вы ищите ложку в кухонном шкафу, а ботинки – на обувной полке, но не обшариваете весь дом. Есть свой порядок и в библиотеке, потому персонал и справляется с работой. Компьютер ищет куда быстрее человека, и все же понуждать его к линейному поиску – проявление крайней жестокости. Впрочем, пострадает не столько компьютер, сколько уснувший в томлении пользователь.

Двоичный поиск

Один удачливый зверолов в минуту откровенности поделился секретом своих успехов. «Вначале я делю лес своей огромной сетью примерно пополам, и выясняю, в которой из двух половин очутился нужный мне зверь – пояснил охотник. – Затем половину со зверем опять делю пополам и гляжу, где он теперь. И так поступаю, пока животное не окажется в тесном загоне». И зверолов нацарапал на песке рис. 90.

Рис.90 – Поимка зайца шестью сетями

Здесь показано, как шестью сетями (они обозначены цифрами) был изловлен несчастный заяц. Обратите внимание на нумерацию сетей, – они расставлялись в этом порядке.

Не воспользоваться ли уловкой зверолова для поиска в массиве? Ускорит ли это дело? Конечно! Но массив должен быть заранее отсортирован. На рис. 91 показан отсортированный по возрастанию массив, содержащий 12 чисел. Для наглядности числа изображены столбиками. Среди них я выбрал наугад число 32, и прямым перебором нашел его позицию (индекс) в массиве. Очевидно, что я выполнил 8 шагов поиска, поскольку число 32 хранится в 8-м элементе массива.

А теперь применим метод зверолова. Обратимся к среднему элементу массива, индекс которого равен полу-сумме первого и последнего индексов, то есть:

(1+12)/2 = 6

Рис.91 – Двоичный поиск в отсортированном массиве

Поскольку индекс – это целое число, дробную часть при делении отбросим. Итак, в позиции 6 оказалось число 21, которое меньше искомого числа 32. Это значит, что «зверь притаился» где-то правее. Раз так, элементы массива, расположенные левее, нас уже не интересуют, – мысленно отбросим их.

С оставшейся частью массива поступим точно так же, то есть, исследуем средний его элемент с индексом

(7+12)/2 = 9

Сравним «живущее» там число 40 с искомым числом 32. На этот раз оно оказалось больше искомого, а значит, искать надо левее, а все, что справа, отбросить. Так, на третьем шаге поиска из 12 элементов массива остались лишь два. Рассуждая тем же порядком, выделяем элемент с индексом

(7+8)/2 = 7

и отбрасываем на этот раз число 27. И вот на последнем четвертом шаге остался лишь один элемент с искомым числом 32.

Подведем итог: вместо 8 шагов последовательного поиска, метод зверолова сделал то же самое за 4 шага. Скажете: всего-то? Восемь шагов или четыре – разница невелика. Так проверим оба метода на большом наборе данных, – поищем в массиве из тысячи чисел. Только избавьте меня от ручной работы, – этот эксперимент поручим компьютеру, для чего соорудим несложную программу.

Исследование двоичного поиска

Частью этой программы будет функция двоичного поиска, алгоритм которой раскрыл зверолов. Но не худо привести и блок-схему этого чудесного изобретения. На блок-схеме (рис. 92), как и в программе, индексы элементов обозначены начальными буквами соответствующих английских слов: L – левый индекс (Left), R – правый индекс (Right), и M – средний индекс (Middle).

Рис.92 – Блок-схема алгоритма двоичного поиска

Функцию, работающую по этому алгоритму, я назвал FindBin (Find – «поиск», Binary – «двоичный»), она показана ниже. Полагаю, что приведенных в ней комментариев будет достаточно.

      { Функция двоичного поиска }
function FindBin (aNum: integer): integer;
var L, M, R : integer; { левый, правый и средний индексы }
begin
      FindBin:= -1;       { результат на случай неудачи }
      L:= 1; R:= CSize;       { начальные значения индексов }
      repeat
      M:= (L+R) div 2;       { индекс среднего элемента }
      if aNum= ArrSort[M] then begin
      FindBin:= M;       { нашли ! }
      Break;       { успешный выход из цикла }
      end;
      if aNum > ArrSort[M] { где искать дальше? }
      then L:= M+1       { ищем правее }
      else R:= M–1; { ищем левее }
      until L > R;       { выход при неудачном поиске }
end;

Теперь мы готовы создать исследовательскую программу, которая будет сравнивать два способа поиска.

Поступим так. Объявим два массива по 1000 чисел в каждом. Заполним их случайным образом и один из них отсортируем. Затем сделаем ряд экспериментов, каждый из которых состоит в следующем. Выбрав наугад одно из чисел массива, программа вызовет по очереди две функции: сначала последовательно найдет число в несортированном массиве, а затем двоичным поиском – в сортированном. Поскольку искомое число выбрано из массива, то поиск всегда будет успешным. Затраченные на поиск шаги подсчитаем, и результаты запишем в текстовый файл. После каждого такого эксперимента программа будет ожидать команды пользователя: приняв число ноль, она завершится, а иначе повторит эксперимент.

Подсчет шагов будем вести в глобальной переменной Steps (шаги). Перед вызовом функций поиска она обнуляется, а внутри функций наращивается (эти операторы внутри функций выделены курсивом). Вот и все, полюбуйтесь на эту «экспериментальную установку», введите в компьютер и запустите на выполнение.

      { P_42_1 – Исследование методов поиска }
const CSize = 1000; { размер массива }
      { объявление типа для массива }
Type TNumbers = array [1..CSize] of integer;
Var ArrRand : TNumbers; { несортированный массив }
      ArrSort : TNumbers; { сортированный массив }
      Steps : integer; { для подсчета числа шагов поиска }
{ Процедура "пузырьковой" сортировки чисел в порядке возрастания }
procedure BubbleSort(var arg: TNumbers);
var i, j, t: Integer;
begin
for i:= 1 to CSize-1 do       { внешний цикл }
      for j:= 1 to CSize-i do { внутренний цикл }
      if arg[j] > arg[j+1] then begin { обмен местами }
      t:= arg[j]; arg[j]:= arg[j+1]; arg[j+1]:= t;
      end;
end;
      { Функция последовательного поиска (Find Sequence) }
function FindSeq (aNum: integer): integer;
var i: integer;
begin
      FindSeq:= -1;       { если не найдем, результат будет -1 }
      for i:=1 to CSize do begin
      Steps:= Steps+1; { подсчет шагов поиска }
      if aNum= ArrRand[i] then begin
      FindSeq:= i;       { нашли, возвращаем позицию }
      Break;       { выход из цикла }
      end;
      end;
end;
      { Функция двоичного поиска (Find Binary) }
function FindBin (aNum: integer): integer;
var L, M, R : integer;
begin
      FindBin:= -1;
      L:= 1; R:= CSize;
      repeat
      Steps:= Steps+1;       { подсчет шагов поиска }
M:= (L+R) div 2;
      if aNum= ArrSort[M] then begin