Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
40.
Бинарный поиск в STL
Все описанные в этом разделе алгоритмы представляют собой версии бинарного поиска. Хотя бинарный поиск обычно весьма эффективен (имеет логарифмическое время работы) только для последовательностей с произвольным доступом (таких как векторы, деки или массивы), алгоритмы написаны так, чтобы могли работать и для последовательностей других видов (таких как списки). В последнем случае время работы алгоритма становится линейно зависящим от размера контейнера, но количество сравнений все равно остается логарифмическим.
Для всех трех алгоритмов предусловием является отсортированность диапазона [first; last) с использованием оператора < или функционального объекта comp в случае, когда алгоритм принимает аргумент типа Compare.
Алгоритм binary_search
Прототипы
template <typename Forwardlterator, typename T>
bool binary_search(Forwardlterator first,
Forwardlterator last, const T& value);
template <typename Forwardlterator, typename T,typename Compare>
bool binary_search(Forwardlterator first,
Forwardlterator last, const T& value, Compare comp);
Алгоритмы binary_search возвращают true, если значение value имеется в диапазоне [first; last), и false в противном случае.
Алгоритм lower_bound
Прототипы
template <typename ForwardIterator, typename T>
ForwardIterator lower_bound(ForwardIterator first,ForwardIterator last,
const T& value);
template <typename ForwardIterator, typename T, typename Compare>
ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last,
const T& value, Compare comp);
Алгоритмы lower_bound возвращают итератор, указывающий на первую позицию в диапазоне [first; last), в которую значение value могло бы быть вставлено без нарушения порядка сортировки.
Алгоритм upper_bound
Прототипы
template <typename ForwardIterator, typename T> ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last, const T& value);
template <typename ForwardIterator, typename T,typename Compare> forwardIterator upper_bound(ForwardIterator first, ForwardIterator last,
const T& value, Compare comp);
Алгоритмы upper_bound возвращают итератор, указывающий на последнюю позицию в диапазоне [first; last), в которую значение value могло бы быть вставлено без нарушения порядка сортировки.
Алгоритм equal_range
Прототипы
template <typename Forwardlterator, typename T>
pair<ForwardIterator, ForwardIterator>equal_range(Forwardlterator first,
Forwardlterator last, const T& value);
template <typename Forwardlterator, typename T,typename Compare> pair<Forwardlterator, ForwardIterator>equal_range(Forwardlterator first,
Forwardlterator last, const T& value, Compare comp);
Функции equal_range возвращают пару итераторов, которые были бы возвращены алгоритмами lower_bound и upper_bound.
Временная сложность
Логарифмическая для последовательностей с произвольным доступом, линейная в противном случае. Количество операций сравнения в любом случае логарифмическое. Для последовательностей, не являющихся последовательностями с произвольным доступом, количество операций ++ линейно, что и делает общее время работы алгоритма линейным.
В случае lower_bound и upper_bound количество сравнений не превышает logN + 1, у binary_search оно не превышает logN + 2, а в случае equal_range оно не выше 21ogN+ 1, где N—размер диапазона [first; last).
Рассмотрим пример программы, в которой используются алгоритмы бинарного поиска STL:
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
vector<int> v(5);
vector<int>::iterator it;
bool found;
int i;
for(i=0;i<5;i++)
{v[i]=2*i;
cout<<v[i]<<'\t';}
cout<<endl;
found=binary_search(v.begin(),v.end(),6);
if(found) cout<<"6: Yes\n";
else cout<<"6: No\n";
found=binary_search(v.begin(),v.end(),7);
if(found) cout<<"7: Yes\n";
else cout<<"7: No\n";
it=lower_bound(v.begin(),v.end(),6);
cout<<it-v.begin()<<endl;
it=upper_bound(v.begin(),v.end(),6);
cout<<it-v.begin()<<endl;
pair<vector<int>::iterator,vector<int>::iterator> pi;
pi=equal_range(v.begin(),v.end(),6);
cout<<"Index <=6: "<<pi.first-v.begin()<<endl;
cout<<"Index >6: "<<pi.second-v.begin()<<endl;
return 0;
}