Печатать эту главуПечатать эту главу

§ 12. Поиск элементов с заданными свойствами

12.2. Поиск одного элемента, удовлетворяющего условию поиска

Пример 12.1. Одномерный массив a состоит из n случайных натуральных чисел (все числа меньше 100). Определить, есть ли в нем хотя бы один элемент, равный x (значение x вводится).

Этапы выполнения задания

I. Исходные данные: массив a, количество чисел n, искомое число x.

II. Результат: вывод сообщения «элемент найден» или «элемент не найден».

III. Алгоритм решения задачи.

1. Ввод количества элементов и генерация элементов массива случайным образом. 
2. Логическая переменная p имеет значение «истина», если элемент в массиве найден, и «ложь» — в противном случае. До просмотра элементов массива p = false. 
3. В цикле будем просматривать все числа в массиве и сравнивать их с числом x. 
4. Поиск заканчивается при выполнении одного из двух следующих условий:

4.1. Элемент найден (p = true), т. е. в массиве есть такой элемент a[i], что a[i] = x.
4.2. Весь массив просмотрен, и совпадения не обнаружено (p = false).

5. Вывод результата.

IV. Описание переменных: n, x – int, p – bool, a – vector <int>.

Часто требуется не только определить, есть ли в массиве искомый элемент, но и установить, на каком месте он находится.

Будем хранить индекс найденного элемента в переменной k, которой до начала просмотра присвоили значение –1 (пример 12.2). После выполнения данного алгоритма по значению переменной k можно определить, есть ли в массиве искомый элемент, и, если есть, то где он стоит. Если в массиве несколько таких элементов, то в переменной k будет храниться номер последнего из них. Если такого элемента нет, то значение переменной k не изменится (k останется равным — 1).

На практике операцию поиска приходится выполнять достаточно часто, и скорость работы программы находится в прямой зависимости от используемого алгоритма поиска.

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

Для сокращения времени поиска можно останавливаться сразу после того, как элемент найден. В этом случае весь массив придется просмотреть только тогда, когда искомый элемент последний или его нет.

Если используется цикл for с условием просмотра всех элементов, то при нахождении элемента нужно прервать выполнение цикла (пример 12.3).

Можно воспользоваться циклом while. Цикл заканчивает работу, когда будет найден искомый элемент либо когда k == n , т. е. элемента, совпадающего с x, нет в массиве (пример 12.4).

При такой реализации на каждой итерации цикла требуется увеличивать индекс k и вычислять логическое выражение. Ускорить поиск можно, упростив логическое выражение. Поместим в конец массива дополнительный элемент со значением х (вектор должен быть описан из n + 1 элемента). Тогда совпадение с х обязательно произойдет, и можно не проверять условие a[k] != x. Такой вспомогательный элемент часто называют барьером или часовым, т. к. он препятствует выходу за пределы массива.

Пример 12.1.

V. Программа:

#include <iostream>

#include <vector>

#include <ctime>

#include <cstdlib>

 

using namespace std;

 

int main()

{

  srand(time(NULL));

  int n;

  cout << "n = ";

  cin >> n;

  vector <int> a(n);

  cout << "chisla:" << endl;

  for (int i = 0; i < n; i++){

    a[i] = rand() % 100 + 1;

    cout << a[i] << " ";

  }

  cout << endl;

  int x;

  cout << "x = ";

  cin >> x;

  bool p = false;

  ///линейный поиск элемента

  for (int i = 0; i < n; i++){

    if (a[i] == x)

      p = true;

  }

  if (p)

    cout << "naiden";

  else

    cout << "ne naiden";

  cout << endl;

  return 0;

}

VI. Тестирование.

Пример 12.2. Фрагмент программы:

int k = -1;

///линейный поиск элемента

for (int i = 0; i < n; i++){

  if (a[i] == x)

    k = i;

}

if (k == -1)

  cout << "ne naiden";

else

  cout << "naiden na meste " << k;

cout << endl;

 

VI. Тестирование.

Пример 12.3. Фрагмент программы:

int k = -1;

///линейный поиск элемента

for (int i = 0; i < n; i++){

  if (a[i] == x){

    k = i;

    break;

  }

}

if (k == -1)

  cout << "ne naiden";

else

  cout << "naiden na meste " << k;

cout << endl;

Пример 12.4. Фрагмент программы:

int k = 0;

///линейный поиск элемента

while (k < n && a[k] != x)

  k++;

if (k == n)

  cout << "ne naiden";

else

  cout << "naiden na meste " << k;

cout << endl;

Пример 12.5. Программа:

#include <iostream>

#include <vector>

#include <ctime>

#include <cstdlib>

 

using namespace std;

 

int main()

{

  srand(time(NULL));

  int n;

  cout << "n = ";

  cin >> n;

  vector <int> a(n + 1);

  cout << "chisla:" << endl;

  for (int i = 0; i < n; i++){

    a[i] = rand() % 100;

    cout << a[i] << " ";

  }

  cout << endl;

  int x;

  cout << "x = ";

  cin >> x;

  int k = 0;

  a[n] = x;

  ///линейный поиск с барьером

  while (a[k] != x)

    k++;

  if (k == n)

    cout << "ne naiden";

  else

    cout << "naiden na meste " << k;

  cout << endl;

  return 0;

}

В примере 12.5 приведена программа решения задачи из примера 12.1, в которой реализован алгоритм поиска с барьером.