Лабораторная работа №15 поиск в статическом одномерном массиве

Цель работы: Закрепление навыков работы с одномерными массивами

Программные средства: MICROSOFT VISUAL STUDIO

15.1 Теоретические сведения

Массив – это структура данных, которая обладает следующими свойствами:

– все элементы массива имеют один и тот же тип;

– массив имеет одно имя для всех элементов;

– доступ к конкретному элементу массива осуществляется по индексу (индексам).

Различают массивы статические и динамические. Размер статических массивов фиксирован, а в динамических массивах число элементов может изменяться в ходе программы.

В языке Си обработка массивов осуществляется по элементам и, как правило, реализуется в цикле.

Рис.15.1. Алгоритм поиска по заданному шаблону

Распространенными методами работы с массивами являются: – поиск; – сортировка: – вставка; – удаление. Для этих методов предложены различные по эффективности алгоритмы реализации. В большинстве случаев нет необходимости «изобретать велосипед», достаточно воспользоваться известными алгоритмами [5]. Выбранные алгоритмы могут различаться по скорости работы и используемым вычислительным ресурсам. Самым простым вариантом поиска можно считать поиск в неупорядоченном одномерном массиве.

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

Классическим алгоритмом поиска в отсортированном массиве является двоичный (бинарный) поиск (также известен как метод деления пополам и дихотомия).

Алгоритм линейного поиска состоит в следующем – поочередно просматриваются элементы, каждый из которых сравнивается с искомым, если они тождественны, то поиск заканчивается, в лучшем случае предстоит произвести всего одно сравнение, а в худшем – n, где n— количество элементов массива. Аналогично ищется максимальный элемент.

Рис. 15.2. Алгоритм линейного поиска

Описание алгоритма. Исходные данные: A[N] – массив из N элементов. Результаты: Amax – максимальное значение L– индекс искомого элемента. Вначале предполагается, что искомый элемент нулевой и текущее значение Amax устанавливается равным ему. Затем каждый элемент массива последовательно сравнивается с Amax. Если текущий элемент больше Amax, то его значение сохраняется в качестве текущего результата. При достижении границы массива текущее значение Amax и соответствующего индекса L становиться результатом. Следует отметить, что для поиска минимума достаточно поменять операцию отношения в условии на «меньше».

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

Алгоритм бинарного поиска:

Шаг 1. Определить номер среднего элемента массива.

Шаг 2. Если значение среднего элемента массива равно искомому, то возвращаем значение, равное номеру искомого элемента, и алгоритм завершает работу.

Шаг 3. Если искомое значение больше значения среднего элемента, то возьмем в качестве массива все элементы справа от среднего, иначе возьмем в качестве массива все элементы слева от среднего (в зависимости от характера упорядоченности).