Песни о Паскале

      { Функция поиска в массиве Numbers позиции числа aNum }
function FindSeq (aNum: integer): integer;
var i: integer;
begin
      FindSeq:= -1;       { если не найдем, то результат будет -1 }
      for i:=1 to Fact do
      if aNum=Numbers[i] then begin
      FindSeq:= i;       { нашли, возвращаем индекс }
      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