Лабораторная работа №11 ПОИСК ПО КЛЮЧУ В ОДНОМЕРНОМ МАССИВЕ СТРУКТУР

11.1. Поиск в массиве

Поиск – это нахождение информации в массиве по заданному значению (ключу).

11.1.1. Линейный поиск (метод полного перебора)

Метод применяется для неупорядоченных массивов и представляет собой

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

до конца массива, если ключ не обнаружен.

И

int P_Lin1(int a[ ], int n, int x)

Р

{

for(int i = 0; i < n; i++)

Г

У

if (a[i] == x) return i;

}

return -1;

а

Эффективность такого алгоритма пропорциональна количеству элементов.

Единственная возможность

улучшить вышеприведенныйБ

алгоритм –

к

уменьшить количество проверок на аждом ш ге. Для этого вводится вспомо-

е

гательный элемент – барьер, который предохр няет от перехода за пределы

массива:

int P_lin2(int a[], int

n, int x)

{

о

a[n+1] = x;

int i = 0;

и

while (a[i] != x) т

л

i++;

if (i == n+1) return -1;

б

else return i;

}

и

Эффект вность этого алгоритма в два раза выше предыдущего.

Б

11.1.2. Двоичный (бинарный) поиск

Применяется только для упорядоченных массивов.

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

45