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

20.3. Бинарный поиск

Если массив отсортирован, то для поиска элемента x можно применять алгоритм бинарного поиска. Алгоритм дихотомии реализован в нескольких функциях:

binary_search

Определяет, присутствует ли элемент в некотором диапазоне

equal_range

Ищет диапазон элементов, равных определенному элементу

lower_bound

Ищет первое место в диапазоне, в которое можно вставить значение, сохраняя упорядоченность

upper_bound

Ищет последнее место, куда можно вставить значения, сохраняя упорядоченность (первое место, в котором элемент больше, чем вставляемое значение)

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

Пример 20.5. Дан линейный отсортированный массив целых чисел. Написать программу, которая получит количество элементов, меньших x и больших y. Массив упорядочен в порядке убывания. Данные прочитать из файла. Числа x и y ввести с клавиатуры.

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

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

II. Результат: количество элементов, меньших x и больших y.

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

1. Ввод исходных данных.
2. Для решения задачи будем использовать алгоритм бинарного поиска.

2.1. Для поиска n1 — номера первого значения, меньшего x, воспользуемся функцией upper_bound. 
2.2. Для поиска n2 — номера первого значения, большего y, воспользуемся функцией lower_bound. 
2.3. Ответом будет значение, равное модулю разности позиций для чисел x и y. 
2.4. Вывод результата.

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

Функция  equal_range  возвращает диапазон, содержащий все элементы, равные x. Диапазон определяется двумя итераторами, первый указывает на первый элемент, не меньший (равный или больше), чем x, второй указывает на первый элемент, больший, чем x. Первый итератор может быть получен использованием  lower_bound(),  второй —   upper_bound().  Возвращаемым значением является тип пара (pair), содержащий два итератора.

Для использования типа данных  pair  необходима библиотека  utility. 

Пример 20.5.

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

#include <iostream>

#include <fstream>

#include <vector>

#include <cmath>

#include <algorithm>

 

using namespace std;

 

int main()

{

  ifstream fin("input.txt");

  int n;

  fin >> n;

  vector <int> a(n);

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

    fin >> a[i];

  int x, y;

  cout << "x, y" << endl;

  cin >> x >> y;

  int n1 = upper_bound(

          a.begin(), a.end(),

          x, greater<int>())

          - a.begin();

  int n2 = lower_bound(

          a.begin(), a.end(),

          y, greater<int>())

          - a.begin();

  cout << n1 << " " << n2 << endl;

  int rez = abs(n2 - n1);

  cout << "mezdu x i y ";

  cout << rez << " chisel";

  cout << endl;

  return 0;

}

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

 

 

Анализ результатов. Значение 7 – номер первого меньшего 88, а значение 8 — номер первого большего 82.