§ 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.