Programowanie c++

Wyszukiwanie binarne lower/upper_bound

Kategoria: Informatyka - strona ogólna kategorii / programowanie c++

Wykorzystanie lower_bound i upper_bound do znalezienia pierwszego i ostatniego miejsca występowania poszukwanego elementu w zestawie danych.

 

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4. using namespace std;
  5.  
  6. int main ()
  7. {
  8.   int T[] = {5,1,2,3,3,2,1,1,5,5,3,4,2,9,9};
  9.   int n=sizeof(T)/sizeof(int);    //obliczamy ilosc el. w tabeli
  10.   vector <int> V (T,T+n);         //umieszczamy dane z tabeli w wektorze
  11.  
  12.   sort (V.begin(), V.end());      //sortujemy elementy w wektorze
  13.  
  14.   cout<<"\n";  //pomoc - przegladamy zawartosc wektora
  15.   for (int i=0 ; i<V.size(); i++)
  16.         cout<<V[i]<<" ";            
  17.  
  18.   int find;
  19.   find=5;  //poszukiwany element
  20.    
  21.   vector<int>::iterator first,last;
  22.   first=lower_bound (V.begin(), V.end(), find);
  23.   last=upper_bound (V.begin(), V.end(), find);
  24.  
  25.   cout << "\n" << "Pierwsze wysytapienie: " << (first - V.begin()) ;
  26.   cout << "\n" << "Pierwszy element (wiekszy) nie spelniajacy zapytania: " << (last - V.begin()) ;
  27. }