Поиск позиции элемента в отсортированном массиве

Для поиска позиции элемента в отсортированном массиве можно использовать метод дихотомии (деления области поиска пополам). В этом методе элемент, который находится в середине области поиска, сравнивается с образцом, который нужно найти. В результате такого сравнения можно определить найден ли отыскиваемый элемент, а если нет, то можно определить, в какой из половин области поиска может находиться искомый элемент, справа или слева. Таким образом, в результате одного сравнения область поиска сужается наполовину.

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

Функция, возвращающая номер позиции элемента в отсортированном массиве приведена ниже. Если элемент не найден, функция возвращает 0.

// Поиск позиции элемента в сортированом массиве

// x – элемент, позицию которого нужно найти

// а – упорядоченный массив, count – число элементов в нем

function FindPosInSortArray (x: integer; a: TArray100; count: integer): integer;

varpos, left, right: integer;

Begin

// left и right – левая и правая границы области поиска

left := 1; right := count;

while left

Begin

// Позиция в середине области поиска

pos:=(right + left) div 2;

if a[pos] = x then begin

{ элемент найден}

result := pos;

exit;

end;

ifx a[pos]

then right := pos – 1 { элемент находится слева}

else left := pos + 1; { элемент находится справа}

end;

// Элемент не найден

result := 0;

end;

Удаление элемента из отсортированного массива

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

Процедура удаления элемента из отсортированного массива приведена ниже.

// Удаление элемента из отсортированного массива

// x – элемент, который нужно удалить

// а – упорядоченный массив, count – число элементов в нем

procedure DelFromSortArray (x: integer; vara: TArray100; var count: integer);

vari,pos, left, right: integer;

Begin

pos := FindPosInSortArray (x,a,count);

if pos = 0then exit;

count := count – 1;

for i := posto count do a[i]:=a[i+1];

end;

8.4 Задание для самостоятельной работы

В лабораторной работе следует создать проект, в соответствии с требованиями варианта из таблицы 8.1. Номер варианта выбирается по последней цифре номера зачетной книжки.

Главное меню проекта должно включать следующие пункты:

– Создание массива

– Сортировка массива

– Вставка элемента в массив

– Удаление элемента из массива

На форме должно быть поле для ввода количества элементов массива и поле для максимального значения числа в массиве (если тип элементов ±Real ).

Ввод удаляемого и вставляемого элемента на усмотрение разработчика.

Компоненты для хранения исходного массива и массива, получаемого в результате обработки, должны соответствовать варианту задания. Глобальные переменные для хранения массива и количества данных в нем использовать не следует. При выполнении каждого пункта меню всю необходимую информацию считывать с формы.

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

8.5 Содержание отчета

– Наименование работы

– Цель работы

– Краткое описание изученных методов сортировки массивов

– Тексты процедур и функций, разработанных самостоятельно

– Результаты тестирования проекта в виде копий экранов

– Выводы

Контрольные вопросы

– Сортировка выбором

– Сортировка обменом

– Сортировка вставкой

– Вставка элемента в отсортированный массив