Учебное пособие C#. Алгоритмы и структуры данных н. А. Тюкачев, В. Г. Хлебостроев издание третье, стереотипное 1 / 23

2.1. А
ЛГОРИТМЫ ПОИСКА
 
Как уже говорилось выше, поиск в отсортированном массиве происхо-
дит гораздо быстрее, чем в массиве неотсортированном. В этих двух случаях 
используются разные алгоритмы поиска. Кроме того, массив изначально мо-
жет заполняться так, чтобы сделать поиск в нем максимально простым. Ниже 
будет описан способ такого заполнения, получивший название хеширование. 
2.1.1. П
ОИСК В НЕУПОРЯДОЧЕННОМ МАССИВЕ
 
Простейшим методом поиска элемента, находящегося в неупорядочен-
ном массиве, является последовательный просмотр каждого элемента масси-
ва. Перебор элементов заканчивается либо тогда, когда найдется элемент с 
искомым ключом, либо когда будет достигнут конец массива – это значит, 
что такого элемента в массиве нет.
15 / 23

---

16 
Результатом поиска желательно иметь индекс искомого элемента, если 
элемент найден. Поэтому алгоритм, осуществляющий поиск элемента в мас-
сиве, оформим в виде статического метода целого типа. Если элемент найден, 
возвращаемое значение равно индексу первого найденного элемента. Если же 
искомого элемента в массиве нет, то метод возвращает значение, равное -1. 
Алгоритм простого поиска элемента x в массиве a приведен в листинге 2.1. 
Листинг 2.1. Простой поиск 
static int SearchSimple(int[] a, int x) 
{ 
int L = a.Length; 
int i = 0; 
// 
с проверкой выхода за границу массива 
while (i < L && a[i] != x)
i++; 
if (i < L) 
// 
если элемент найден, возвращаем его индекс 
return i;
else 
// 
если элемент не найден, возвращаем -1 
return -1;
} 
В этом алгоритме выход из цикла осуществляется по двум условиям: 
элемент найден или достигнут конец массива. Проверку выхода за границу 
массива можно опустить, если искомый элемент гарантированно находится в 
массиве. Такой гарантией может служить барьер – дополнительный элемент 
массива, значение которого равно искомому элементу. Установка барьера 
производится до цикла поиска.