Песни о Паскале
Шрифт:
const CNumbers = 100; { размер массивов }
type TNumbers = array[1..CNumbers] of integer;
TNames = array[1..CNumbers] of string;
var Numbers : TNumbers; { массив номеров автомобилей }
Names : TNames; { массив сведений о владельце }
Здесь добавлен массив Names (имена), содержащий столько же строк, сколько номеров в базе данных. Эти строки соответствуют элементам массива номеров Numbers. Так, если элемент Numbers[7] содержит число 123, а элемент Names[7] – строку «Горбунков С.С., тел. 11-22-33», то значит, гражданин
Что связывает массивы Names и Numbers? Ответ очевиден – общий индекс. Определив индекс автомобиля в массиве номеров, мы получим доступ и к сведениям о его владельце в строковом массиве.
Последовательный поиск
Напомню, что в полицейской базе данных из 40-й главы заголовок функции поиска был таким.
function FindNumber(aNum: integer): boolean;
Функция FindNumber выясняет, существует ли искомый номер в массиве Numbers, то есть она дает булев результат. Теперь этого мало, – хочется получить индекс элемента, где хранится искомый номер. А если такого номера в массиве нет? Пусть тогда функция вернет некоторое условное значение, например, минус единицу.
С учетом этих пожеланий, напишем новую функцию поиска и дадим ей имя FindSeq (от слов Find – «искать», Sequence – «последовательно»).
{ Функция поиска в массиве 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 – Поимка зайца шестью сетями
Здесь показано, как шестью сетями (они обозначены цифрами) был изловлен несчастный заяц. Обратите внимание на нумерацию сетей, – они расставлялись в этом порядке.
Не воспользоваться ли уловкой зверолова для поиска в массиве? Ускорит ли это дело? Конечно! Но массив должен быть заранее отсортирован. На рис. 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).