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

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

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

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

// Простой поиск элемента в массиве 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).

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

// Дихотомический поиск элемента в массиве 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);

}

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