Материал: Мансуров. Основы программирования в среде Lazarus. 2010

4.2 Алгоритмы поиска

____________________________________________________________________

readkey;

end.

Как всегда, ищем возможность улучшения программы. В предыдущей про-

грамме пользователь сам вводил индекс в массиве, куда нужно вставить новый элемент. Оказывается, алгоритм бинарного поиска позволяет автоматически вставлять новый элемент в нужное место. Каким образом? Рассмотрим на кон-

кретном примере. Пусть имеется массив из 5 элементов. Необходимо вставить число 3. Вспомним алгоритм бинарного поиска. Первоначальное расположение

При этом значения переменных будут равны:

key = 3, left = 0 (не забывайте, нумерация в динамических массивах с нуля!) right = 4, middle = (left+right) div 2 = (0 + 4) div 2 = 2

a[middle] = a[2] = 4

key = 3 < a[2] = 4, т.е. значение ключа меньше значения среднего элемента.

Согласно алгоритму, переменной right будет присвоено значение:

right = middle - 1 = 2 - 1 = 1

middle = (left+right) div 2 = (0 + 1) div 2 = 1

Новое расположение указателей показано на рисунке 4.13.

1 2 4 5 6

left middle right

Рис. 4.13. Новое расположение указателей

326

Глава 4 Типовые алгоритмы обработки информации

____________________________________________________________________

a[middle] = a[1] = 2

key = 3 > a[1] = 2, т.е. значение ключа больше значения среднего элемента,

следовательно, переменной left будет присвоено значение left = middle + 1 = 1 + 1 = 2

Значение left оказывается больше right: left = 2 > right = 1

Алгоритм поиска заканчивает свою работу, искомый элемент не найден.

Но, посмотрите чему равно значение left. Оно равно 2, т.е. как раз тому индексу

вмассиве, куда должен быть помещен новый элемент, т.е. key равный 3!

Валгоритме достаточно изменить один оператор, в том месте, где функция

BinarySearch возвращает -1 (элемент не найден!), т.е. вместо

BinarySearch:= -1;

необходимо записать

BinarySearch:= left;

Итак, улучшенная программа предыдущего примера. В этой программе вставка нового элемента оформлена в виде процедуры. Кроме того, введены проверки на правильность ввода размера массива

program modify_insert;

uses

CRT, FileUtil;

var

i: integer;

a: array of integer;

NewElement: integer;

327

4.2 Алгоритмы поиска

____________________________________________________________________

IndexOfNewElement: integer; SizeOfArray: integer; answ: char;

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:= left;

end;

procedure insert_new_element(var a: array of integer;

var NewElement: integer; var IndexOfNewElement: integer); begin

for i:= SizeOfArray - 1 downto IndexOfNewElement do

328

Глава 4 Типовые алгоритмы обработки информации

____________________________________________________________________

a[i + 1]:= a[i];

a[IndexOfNewElement]:= NewElement;

if IndexOfNewElement= SizeOfArray then

inc(SizeOfArray);

end;

begin

writeln(UTF8ToConsole('Введите размер массива')); while true do

begin readln(SizeOfArray); if SizeOfArray = 0 then begin

writeln(UTF8ToConsole('Размер массива не может быть = 0')); writeln(UTF8ToConsole('Введите размер массива'));

end else

if SizeOfArray < 0 then begin

writeln(UTF8ToConsole('Размер массива не может быть < 0')); writeln(UTF8ToConsole('Введите размер массива'));

end

else break; end;

SetLength(a, SizeOfArray); writeln(UTF8ToConsole('Введите элементы массива')); for i:= 0 to SizeOfArray - 1 do

read(a[i]); writeln(UTF8ToConsole('Введен массив:')); for i:= 0 to SizeOfArray - 1 do

329

4.2 Алгоритмы поиска

____________________________________________________________________

write(a[i], ' '); writeln; writeln(UTF8ToConsole('Откорректируйте данные')); writeln(UTF8ToConsole('Если все правильно, нажмите Enter,')); writeln(UTF8ToConsole('иначе - любую клавишу'));

answ:= readkey;

if answ = #13 then exit; writeln(UTF8ToConsole('Введите новый элемент')); readln(NewElement);

IndexOfNewElement:= BinarySearch(a, NewElement); insert_new_element(a, NewElement, IndexOfNewElement);

writeln(UTF8ToConsole('Массив после вставки нового элемента'));

for i:= 0 to SizeOfArray - 1 do

write(a[i], ' '); writeln;

writeln(UTF8ToConsole('Нажмите любую клавишу'));

readkey;

end.

В программе предполагается, что первоначальный размер массива не дол-

жен изменяться. Если вы помните, в примере мы моделировали ситуацию, ко-

гда пользователю необходимо было откорректировать ошибочно введенные данные. Если же вам нужно, чтобы вставляемый элемент расширял исходный массив, вам нужно в процедуре insert_new_element заменить условный оператор

if IndexOfNewElement = SizeOfArray then inc(SizeOfArray);

на просто оператор инкремента

330