Линейный поиск в массиве

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

Линейный поиск – простейшая разновидность алгоритмов поиска данных.

Например, если нам требуется найти число 5 в массиве из 15 элементов, то мы начинаем поиск с элемента с номером 0 и последовательно проверяем каждый элемент на равенство числу 5. Если совпадение найдено – необходимо запомнить номер элемента и завершить цикл поиска.

Ввиду простоты алгоритма его псевдокод и реализация не приводятся и предлагаются для самостоятельной работы.

Двоичный поиск в массиве

Если у нас есть массив, содержащий упорядоченную последовательность данных, то очень эффективен двоичный поиск.

Переменные lowerBound и upperBound содержат, соответственно, левую и правую границы отрезка массива, где находится нужный нам элемент. Мы начинаем всегда с исследования среднего элемента отрезка. Если искомое значение меньше среднего элемента, мы переходим к поиску в верхней половине отрезка, где все элементы меньше только что проверенного. Другими словами, значением upperBound становится (M – 1) и на следующей итерации мы работаем с половиной массива. Таким образом, в результате каждой проверки мы вдвое сужаем область поиска. Так, в нашем примере, после первой итерации область поиска – всего лишь три элемента, после второй остается всего лишь один элемент. Таким образом, если длина массива равна 6, нам достаточно трех итераций, чтобы найти нужное число.

Двоичный поиск - очень мощный метод. Если, например, длина массива равна 1023, после первого сравнения область сужается до 511 элементов, а после второй - до 255. Легко посчитать, что для поиска в массиве из 1023 элементов достаточно 10 сравнений.

Алгоритм двоичного поиска приведен ниже:

lowerBound = 0

upperBound = size

Повторять бесконечно

M = (lowerBound + upperBound) / 2

Если K < A[M], то

upperBound = M – 1

Иначе Если K > A[M], то

lowerBound = M + 1

Иначе

Сообщить «Элемент найден, его индекс: », M

Выход из цикла

Все если

Если lowerBound > upperBound, то

Сообщить «Элемент не найден»

Выход из цикла

Все если

Все повторять

В описанном выше алгоритме приняты следующие условия:

1. size – размер массива

2. K – число, которое нужно найти

3. М – индекс найденного элемента.

Инициализация массива случайными числами

Для выполнения лабораторной работы №3 придется пользоваться массивами большого размера. Размеры массивов в данной работе могут достигать 15 тысяч элементов, что не позволяет реализовать ввод данных с клавиатуры. Для решения этой задачи предлагается использовать инициализацию массива случайными числами.

Для работы с генератором случайных чисел необходимо создать объект стандартного класса Random:

Random Rnd = new Random();

Инициализация массива выполняется с помощью метода Next класса Random и может выглядеть следующим образом:

int maxValue = 100;

int[] a = new int[1000];

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

a[i] = Rnd.Next(0, maxValue); // Случайное число от 0 до 100