Линейный поиск (поиск в лоб) в массивах в С++

Линейный поиск в массивах, или как его ещё называют, поиск в ЛОБ  эффективен в массивах, с небольшим количеством элементов, причём элементы в таких массивах никак не отсортированы и не упорядочены. Алгоритм линейного поиска в массивах последовательно проверяет все элементы массива и сравнивает их с ключевым значением. Таким образом, в среднем необходимо проверить половину значений в массиве, чтобы найти искомое значение. Чтобы убедиться, в отсутствии искомого значения необходимо проверить все элементы массива. Разработаем программу, которая ищет минимальное значение в массиве. Поиск в программе реализован согласно алгоритму линейного поиска в массиве.

// min_max.cpp: определяет точку входа для консольного приложения.
// поиск минимального значения в одномерном масиве

#include "stdafx.h"
#include <iostream>
#include <ctime>
using namespace std;

int main(int argc, char* argv[])
{
    srand(time(0));
    const int array_size = 25; // размер одномерного массива
    int array1[array_size]; // объявление одномерного массива
    for (int counter = 0; counter < array_size; counter++)
    {
     array1[counter] = rand() % 50 - rand() % 50; // заполняем массив случайными значениями в диапазоне от -49 до 49 включительно
     cout << array1[counter] << " "; // печать элементов одномерного массива array1 
    }
    int min = array1[0]; // переменная для хранения минимального значения
    for (int counter = 1; counter < array_size; counter++)
    {
     if ( min > array1[counter] ) // поиск минимального значения в одномерном массиве
         min = array1[counter]; 
    }
    cout << "nmin = " << min << endl;
    system("pause");
    return 0;
}

В строке 12 объявлена переменная с квалификатором const. В цикле for  строки 14  — 18 заполняется массив array1 и сразу же печатаются значения элементов массива. Два действия объединены в один цикл, таким образом не надо объявлять отдельный цикл для вывода значений массива. В строке 19 объявлена переменная min для хранения минимального значения, которое будет найдено в ходе линейного поиска в массиве. Причём переменная min инициализирована первым значением массива, так как перед сравнением необходимо сначала инициализировать переменную. В строках 20 — 24 объявлен цикл for, в котором будет выполнятся алгоритм линейного поиска в массивах. Переменная-счётчик в цикле for инициализирована единицей, то есть обработка массива начнётся со второго элемента, ведь первый элемент массива уже содержится в переменной min  В теле цикла объявлен оператор условного выбора if, который будет последовательно сравнивать значение в переменной min со значениями элементов массива array1.  В каждой итерации цикла будет выполнятся проверка условия в строке 22, и если условие истинно, то в переменную min будет записываться всё меньшее и меньшее значение, если таковое окажется в массиве. В противном случае значение в переменной min меняться не будет. Результат работы алгоритма линейного поиска в массиве (см. Рисунок 1).

поиск в массивах С++

Рисунок 1 — Поиск в массивах С++

Как показала программа, значение -26 — это минимальное значение массива array1.

Мы знаем как искать минимальное значение в массиве, используя алгоритм линейного поиска в массиве. Переделаем эту программу так, чтобы она искала максимальное значение в массиве. Всё, что нужно изменить, так это знак строгого отношения, в операторе условного выбора if, на противоположный, строка 22.

// фрагмент кода (линейный поиск в массиве)
 if ( max < array1[counter] ) // поиск максимального значения в одномерном массиве

Теперь  мы знаем, как быстро и легко переделать алгоритм линейного поиска в массивах минимального значения на алгоритм линейного поиска в массивах максимального значения. Мы организовали линейный поиск в одномерном массиве, в двумерных массивах алгоритм линейного поиска не изменится. Рассмотрим фрагмент кода — алгоритм линейного поиска в двумерном массиве.

int min = array1[counter_string][counter_column]; // переменная для хранения минимального значения
for (int counter_string = 0; counter_string < counter_string; counter_string++)
    {
         for (int counter_column = 0; counter_column < counter_column; counter_column++)
                 {
                if ( min > array1[counter_string][counter_column] ) // поиск минимального значения в двумерном массиве
            min = array1[counter_string][counter_column]; 
                 }
    }

В строке 1 мы инициализируем переменную min первым значением двумерного массива array1, для того, чтобы избежать логических ошибок. Фактически  переменную min можно не инициализировать, и программа будет работать правильно. Но существует вероятность возникновения логической ошибки, то есть программа сработает, но сработает не правильно. Суть в том, что при объявлении переменной, в ней изначально будет содержаться какое-то значение(это значение называют мусор), и в зависимости от того, какое значение будет содержаться в переменной изначально, без принудительной инициализации этой переменной, программа будет работать не правильно. Так как будет сравнивать значения массива с мусором. Обычно мусор всегда положительный, а значит минимальное значение в массиве будет искаться безошибочно. В случае с алгоритмом линейного поиска в массиве максимального значения, программа всегда будет срабатывать не правильно. Именно по этому мы принудительно инициализируем переменную min или max начальным значением. тогда возникает вопрос: «Каким значением инициализировать эту переменную?». Да всё просто, инициализируем переменную min любым значением из массива. Да, не обязательно выполнять инициализацию первым значением из массива, можно взять любое. Но для простоты советую брать первое значение массива. Алгоритм линейного поиска в двумерном массиве не сильно изменился, а точнее, вообще не изменился. Добавился ещё один цикл for, ведь поиск выполняется в двумерном массиве.

Если у вас есть отсортированный массив, то самый лучший алгоритм поиска — бинарный поиск, о котором вы можете почитать тут.

Автор: admin
Дата: 26.08.2012
Поделиться:

Комментарии

Оставить комментарий

Вы должны войти, чтобы оставить комментарий.