§ 20. Использование библиотечных функций для сортировки и поиска данных

20.1. Линейный поиск элемента

Для организации линейного поиска элемента в массиве можно использовать следующие функции:

find

Находит значение в данном диапазоне

count

Возвращает количество элементов, соответствующее данному значению

find_if

Ищет первое вхождение элемента, для которого верно значение функции компаратора

count_if

Возвращает количество элементов, для которых значение функции компаратора является истиной

У всех этих функций три параметра. Первые два параметра являются итераторами, которые определяют диапазон для поиска в массиве, третий задает условие поиска. При этом левая граница диапазона входит в область поиска, а правая — нет. То есть диапазон поиска является полуинтервалом. Если поиск осуществляется во всем векторе, то используются итераторы begin() и end().

В качестве результата функции find и find_if выдают значение итератора, указывающего на первый элемент, соответствующий поисковому запросу.

Компаратор для функций, реализующих поиск элемента в диапазоне, имеет один параметр. Компаратор возвращает значение true, если элемент удовлетворяет условию поиска, и false, если нет. Функция поиска передает в компаратор поочередно значения из диапазона поиска. Как только для какого-то значения получили true, работа поисковой функции прекращается.

Если элемент не найден, функция возвращает итератор на правую границу области поиска.

Пример 20.1. Дан линейный массив целых чисел. Написать программу, которая:

1) найдет позицию элемента, равного x;

2) найдет позицию элемента, кратного x;

3) посчитает количество элементов, равных x;

4) посчитает количество элементов, кратных x.

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

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

II. Результат: позиции элементов n1 и n2 (пункты 1 и 2) и количество элементов k1 и k2 (пункты 3 и 4).

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

1. Ввод исходных данных. Данные сгенерируем случайным образом.
2. Будем использовать следующие функции:

2.1. find для пункта 1.
2.2. find_if для пункта 2.
2.3. count для пункта 3.
2.4. count_if для пункта 4.

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

IV. Описание переменных: n, k1, k2, n1, n2, x – int, a –  vector<int>.

Функции min_element и max_element возвращают итератор на минимальное и максимальное значения элементов в диапазоне.

Пример 20.2. Дан линейный массив целых чисел. Написать программу, которая найдет минимальный и максимальный элементы в массиве.

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

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

II. Результат: позиции минимального и максимального элементов nmin и nmax и их значения.

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

1. Ввод исходных данных. Данные сгенерируем случайным образом.
2. Будем использовать соответствующие функции.
3. Вывод результата.

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

Пример 20.1.

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

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstdlib>

#include <ctime>

 

using namespace std;

 

int x;

 

bool comp(int t)

{

  return (t % x == 0);

}

 

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;

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

  }

  cout<<endl;

//поиск элемента x в массиве

  cout << "x = ";

  cin >> x;

  int n1 = find(a.begin(), a.end(), x) - a.begin();

  if(n1 < a.size())

    cout << "chislo na meste " << n1 << endl;

  else

    cout << "net chisla = x" << endl;

//поиск по условию: число кратно x

  int n2 = find_if(a.begin(), a.end(), comp) - a.begin();

  if (n2 < a.size()){

    cout << "chislo " << a[n2];

    cout << " na meste " << n2;

    cout << endl;

  }

  else

    cout << "net kratnyh chisel" << endl;

//количество элементов, равных х

  int k1 = count(a.begin(), a.end(), x);

  cout << "ravno x - " << k1 << endl;

//количество элементов, кратных х

  int k2 = count_if(a.begin(), a.end(), comp);

  cout << "kratno x - " << k2 << endl;

  return 0;

}

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

Анализ результатов. Индекс числа 3 в массиве равен 1, а также это число кратно самому себе. В массиве одно число, равное 3, и два числа (3 и 18), кратных 3.

Обратите внимание на то, что переменная x описана как глобальная переменная, поскольку она используется как в функции main, так и в компараторе comp.

Пример 20.2.

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

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstdlib>

#include <ctime>

 

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;

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

  }

  cout<<endl;

  //поиск минимального и 

  //максимального

  int nmin = min_element(a.begin(), a.end()) - a.begin();

  cout << "min element = " << a[nmin];

  cout << " na meste - " << nmin << endl;

  int nmax = max_element(a.begin(), a.end()) - a.begin();

  cout << "max element = " << a[nmax];

  cout << " na meste - " << nmax << endl;

  return 0;

}

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

Функции  min_element  и  max_element   могут иметь третий параметр — компаратор, определяющий правило порядка для элементов указанного диапазона.