17
//
увеличиваем размер массива на 1
Array.Resize
(ref a, ++L);
a[L - 1] = x; //
устанавливаем барьер
int i = 0;
//
без проверки выхода за границу массива
while (a[i] != x)
i++;
if (i < L - 1)
return i;
else
return -1;
}
В этом примере для изменения размера массива использован обобщен-
ный статический метод Resize класса Array из пространства имен Sys-
tem
. Благодаря наличию барьера в условии продолжения для цикла отсутст-
вует проверка выхода за границу массива.
В алгоритмах поиска основной выполняемой операцией является срав-
нение. Очевидно, что при последовательном поиске в среднем требуется
(N+1)/2
сравнений. Таким образом, данный алгоритм характеризуется ли-
нейной функцией скорости роста – O(N).
2.1.2. П
ОИСК В УПОРЯДОЧЕННОМ МАССИВЕ
Поиск можно значительно ускорить, если массив упорядочен, напри-
мер, по возрастанию. В этом случае чаще всего применяется метод деления
пополам или бинарный поиск. Суть этого метода заключается в следующем.
Сначала искомый элемент сравнивается со средним элементом массива. Если
искомый элемент больше среднего, то поиск продолжается в правой части
массива, если меньше среднего – то в левой части. При каждом сравнении из
рассмотрения исключается половина элементов – не имеет смысла искать
элемент больше среднего в левой части, содержащей меньшие значения.
Максимальное число требующихся сравнений равно log
2
N
. Алгоритм
приведен в листинге 2.3.
Do'stlaringiz bilan baham: 
