4.2 Алгоритмы поиска
____________________________________________________________________
begin
for i:= 0 to High(not_sorted_array) do begin
if name_manager = not_sorted_array[i].name then begin
LinearSearch := i; exit;
end;
end; LinearSearch:= -1; end;
{ ================================== }
begin
{При необходимости укажите полный путь к файлу
или скопируйте файл в папку с данным проектом}
if not FileExists('File_not_sorted.dat') then
begin
writeln(UTF8ToConsole('Файл не существует'));
writeln(UTF8ToConsole('Сначала создайте его'));
writeln(UTF8ToConsole('Нажмите любую клавишу'));
readkey;
exit;
end;
AssignFile(f_not_sorted,'File_not_sorted.dat');
Reset(f_not_sorted);
// Определение количества записей в файле
n:= System.FileSize(f_not_sorted);
SetLength(vector, n);
316
Глава 4 Типовые алгоритмы обработки информации
____________________________________________________________________
{Подготовка поиску,
считывание записей файла в массив,
в функцию передается массив, а не файл.}
i:= 0;
while not Eof(f_not_sorted) do begin
Read(f_not_sorted, company);
vector[i]:= company; // массив, в которым будет вестись поиск i:= i + 1;
end; CloseFile(f_not_sorted);
writeln(UTF8ToConsole('Введите фамилию менеджера')); readln(name_manager);
{вызов функции поиска}
n:= LinearSearch(vector, name_manager);
name_file:= 'File_not_sorted.dat';
{Вызов процедуры для вывода на экран списка менеджеров.
Процедура находится в модуле OutScr}
output_to_screen(name_file);
if n= -1 then
writeln(UTF8ToConsole('Такого менеджера нет'))
else
writeln(UTF8ToConsole('Менеджер найден, его номер '),
n+1);
write(UTF8ToConsole('Нажмите любую клавишу'));
readkey;
end.
Очевидно, что время поиска по этому алгоритму зависит от размера масси-
317
4.2 Алгоритмы поиска
____________________________________________________________________
ва – количества его элементов n. Т.е. этот алгоритм принадлежит классу O(n).
Если массив неупорядочен, то единственный способ найти какой-либо элемент, это линейный поиск. Если же массив упорядочен, то существуют бо-
лее быстрые и эффективные алгоритмы. Наиболее часто используемым являет-
ся алгоритм двоичного (бинарного) поиска. Его также часто называют метод деления пополам.
Суть метода в том, что, пользуясь тем, что массив отсортирован, вместо просмотра подряд всех элементов массива, находим элемент, находящийся по-
середине массива. Назовем его средним элементом (не по значению, а по месту в массиве). Затем сравниваем искомый элемент с этим средним элементом. Ес-
ли искомый элемент меньше среднего, то искать теперь его следует только сре-
ди тех, которые меньше среднего. Таким образом, диапазон поиска уменьшает-
ся ровно наполовину. Берем ту половину массива, где следует искать наш эле-
мент и опять находим средний элемент, опять его сравниваем с искомым эле-
ментом и вновь суживаем зону поиска наполовину и т.д. продолжаем процесс до тех пор, пока в рассматриваемых подмассивах не останется один элемент.
Если он равен искомому, значит элемент найден, если не равен, значит такого элемента в массиве нет.
При выполнении алгоритма в каждом следующем цикле размер массива уменьшается в два раза, отсюда оценка скорости работы алгоритма O(log2n).
Напишем программу бинарного поиска в массиве целых чисел:
program search_in_array; {$mode objfpc}{$H+} uses
CRT, FileUtil; const SizeOfFile= 9; var
a: array[0..SizeOfFile] of integer =
318
Глава 4 Типовые алгоритмы обработки информации
____________________________________________________________________
(1, 2, 3, 4, 5, 6, 7, 8, 9, 10); n: integer;
key: integer;
{ ======== Бинарный поиск ======== }
function BinarySearch(var a: array of integer; key: integer): integer;
var
left, right, middle: integer; begin
left:= Low(a); right:= High(a); repeat
middle:= (left + right) div 2; if key < a[middle] then
right:= middle - 1 else
if key > a[middle] then left:= middle + 1
else begin
BinarySearch:= middle; exit;
end;
until left > right; BinarySearch:= -1;
end;
{ ========================================== }
319
4.2 Алгоритмы поиска
____________________________________________________________________
begin
writeln(UTF8ToConsole('Введите ключ для поиска'));
readln(key);
{вызов функции поиска}
n:= BinarySearch(a, key);
if n= -1 then
writeln(UTF8ToConsole('Такого элемента в массиве нет'))
else
writeln(UTF8ToConsole('Элемент найден, его номер '), n); writeln(UTF8ToConsole('Нажмите любую клавишу'));
readkey;
end.
Напишем программу поиска в файле менеджеров по фамилии бинарным методом:
program search_in_file; uses
CRT, FileUtil, SysUtils, OutScr; type
manager= record name: string[18]; comp: integer;
end; var
company: manager;
f_not_sorted, f_sorted: File of manager; vector: array of manager;
i, n: integer;
320