Лабораторный практикум по информатике

Поиск элемента

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

// Простой поиск элемента в массиве

int IndexOf(ref int[] Array, int Value)

{

// Перебираем все элементы массива

// Нашли нужное значение? Возвращаем его индекс

if (Array[i] == Value) return i;

// Перебор закончился безрезультатно – возвращаем –1 return –1;

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

Вычислительная сложность алгоритма простого поиска – линей- ная O(n).

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

// Дихотомический поиск элемента в массиве

int IndexOf(ref int[] Array, int Value, int Left, int Right)

{

// Находим середину диапазона

// Если нашли значение – возвращаем его индекс

if (Array[x] == Value) return x;

// Если середина совпадает с левой или

// правой границами – значение не найдено

if ((x == Left) || (x == Right)) return –1;

// Продолжаем поиск слева или справа от середины

if (Array[x] < Value)

return IndexOf(ref Array, Value, x, Right); else

return IndexOf(ref Array, Value, Left, x);

}

Вычислительная сложность алгоритма – логарифмическая.