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



бет68/83
Дата06.01.2022
өлшемі1.1 Mb.
#15674
түріПрактикум
1   ...   64   65   66   67   68   69   70   71   ...   83

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


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

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

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

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

}

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




Достарыңызбен бөлісу:
1   ...   64   65   66   67   68   69   70   71   ...   83




©emirsaba.org 2022
әкімшілігінің қараңыз

    Басты бет