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

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

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

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

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

{

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

for (int i = 0; i < Array.Length; i++)

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

if (Array[i] == Value)

return i;

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

return -1;

}

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

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

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

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

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

int Left, int Right)

{

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

int x = (Left + Right) / 2;

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

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);

}

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