Простой поиск в массиве

Во многих задачах требуется последовательно перебрать все элементы массива и найти нужные нам. Мы рассмотрим четыре таких задачи:

• поиск одного заданного элемента;

• вывод всех элементов, которые удовлетворяют заданному условию;

• формирование нового массива из всех отобранных элементов;

• поиск минимального (максимального) элемента.

Все эти задачи решаются с помощью цикла, в котором перебираются все элементы массива от начального (0-ого) до конечного (N-1-ого) элемента. Такой поиск называется линейным, поскольку все элементы просматриваются последовательно один за другим.

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

Пример. Определить, есть ли в массиве элемент с заданным значением x, и, если он есть, найти его номер. Если нет никакой информации о расположении элементов массива, то применяется линейный поиск, основная идея которого – последовательно просматривать массив, пока не будет обнаружено совпадение или не будет достигнут конец массива. Это реализует следующая простая программа:

Чтобы определить ситуацию, когда элемент не найден, нам надо ввести специальную переменную success, которая устанавливается в 1, если элемент найден, и остается равной нулю, если в массиве нет нужного элемента. Такая переменная называется флагом, флаг может быть установлен (равен 1) или сброшен (равен нулю).

Для линейного поиска в худшем случае мы имеем N сравнений. Понятно, что для ускорения поиска надо сначала как-то упорядочить данные, в этом случае можно сделать поиск эффективным.

Поиск всех элементов, соответствующих условию

Пример. Определить, сколько в массиве положительных элементов и вывести их на экран. Для решения этой задачи вводим счетчик – специальную переменную, значение которой будет увеличиваться на единицу, когда мы нашли очередной положительный элемент.

Формирование массива по заданному условию

Пример. Сформировать новый массив B, включив в него все положительные элементы исходного массива A, и вывести его на экран.

Пусть есть массив A[N]. Надо выбрать из него все положительные элементы и записать их в новый массив, который и будет дальше использоваться. Сначала надо определить, сколько места в памяти надо выделить для массива B. В «худшем» случае все элементы в массиве A будут положительными и войдут в массив B, поэтому массив B должен иметь такой же размер, что и массив A.Можно предложить такой способ: просматривать весь массив A, и если для очередного элемента A[i]>0, его значение копируется в B[i].

Однако в этом случае использовать такой массив B очень сложно, потому что нужные элементы стоят не подряд. Есть более красивый способ. Объявляем временную переменную-счетчик count, в которой будем хранить количество найденных положительных элементов. Сначала она равна нулю. Если нашли очередной положительный элемент, то ставим его в ячейку B[count] и увеличиваем счетчик. Таким образом, все нужные элементы стоят в начале массива B.

Минимальный элемент

Пример. Найти и вывести на экран минимальный элемент в массиве A.

Для решения задачи надо выделить в памяти ячейку (переменную) для хранения найденного минимального значения. Сначала мы записываем в эту ячейку первый элемент (A[0]).

Затем берем следующий элемент и сравниваем его с минимальным. Если он меньше минимального, записываем его значение в ячейку минимального элемента. И так далее. Когда мы рассмотрим последний элемент в массиве, в дополнительной ячейке памяти будет минимальное значение из всех элементов массива.

Заметим, что перебор в цикле начинается с элемента с номером 1 (а не 0), поскольку начальный элемент мы рассмотрели отдельно.

Чтобы найти максимальный элемент, достаточно изменить условие в заголовке условного оператора на обратное (A[i] > min). Конечно, вспомогательную переменную в этом случае лучше(но не обязательно!) назвать max.

Теперь можно усложнить задачу и найти еще и номер минимального элемента.

Пример. Найти и вывести на экран минимальный элемент в массиве A и его номер.

Напрашивается такое решение: завести еще одну переменную, в которой хранить номер

минимального элемента. Если мы нашли новый минимальный элемент, то в одну переменную записали его значение, а во вторую – его номер. Тем не менее, можно обойтись одной дополнительной переменной. Дело в том, что по номеру элемента можно легко найти его значение в массиве. На этом основана приведенная ниже программа. Теперь мы запоминаем (в переменной nMin) не значение минимального элемента, а

только его номер.