STL中對于有序序列（vector,list等）提供了相當相當強大的二分搜索Binary search算法。對于可以隨機訪問容器（如vector等），binary search負載度為對數級別（LogN)，對于非隨機訪問容器（如list），則算法復雜度為線性。現在簡要介紹一下幾種常用的binary search算法：
ForwardIterator lower_bound (ForwardIterator first,ForwardIterator last, const T& value)
ForwardIterator lower_bound (ForwardIterator first,ForwardIterator last, const T& value, Compare comp)
//查找最遠的一個iterator i， 使得[first,i)里面的任意一個iterator j，有 *j < value or comp(*j,value)==true.
ForwardIterator upper_bound (ForwardIterator first,ForwardIterator last, const T& value)
ForwardIterator upper_bound (ForwardIterator first,ForwardIterator last, const T& value, Compare comp)
//查找最遠的一個iterator i， 使得[first,i)里面的任意一個iterator j，有 !(*j < value) or comp(*j,value)==false.
pair equal_range(ForwardIterator first, ForwardIterator last, const T& value)
pair equal_range(ForwardIterator first, ForwardIterator last, const T& value, Compare comp)
//查找最大的subrange[i,j)，使得任意一個iterator in [i,j)滿足!(*k<value) && !(value<*k) or comp(*k,value)==false && comp(value,*k)==false.
bool binary_search (ForwardIterator first, ForwardIterator last, const T& value)
bool binary_search (ForwardIterator first, ForwardIterator last, const T& value, Compare comp)
// 查找是否在[first,last)中存在iterator i,滿足 !(*i<value) && !(value<*i) or comp(*i,value)==false && comp(value,*i)==false
// 存在則返回true,否則返回false.
#include<algorithm>
#include<iostream>
#include<vector>
#include<iterator>
using namespace std;
int main()
{
vector<int>v;
vector<int>::iterator itr;
pair< vector<int>::iterator, vector<int>::iterator >vecpair;
for(int i = 1; i <= 20; i++){
v.push_back(i%6);
}
sort(v.begin(),v.end());
cout << "array: " << endl << " ";
copy(v.begin(),v.end(),ostream_iterator<int>(cout," "));
cout << endl;
//lower_bound
cout << "lower_bound function, value = 3:" << endl;
itr = lower_bound(v.begin(),v.end(),3);
cout << " [first, itr) = ";
copy(v.begin(),itr,ostream_iterator<int>(cout," "));
cout << endl;
cout << " [itr, last) = ";
copy(itr,v.end(),ostream_iterator<int>(cout," "));
cout << endl << endl;
// upper_bound
cout << "upper_bound function, value = 3:" << endl;
itr = upper_bound(v.begin(),v.end(),3);
cout << " [first, itr) = ";
copy(v.begin(),itr,ostream_iterator<int>(cout," "));
cout << endl;
cout << " [itr, last) = ";
copy(itr,v.end(),ostream_iterator<int>(cout," "));
cout << endl << endl;
// equal_range
cout << "equal_range function, value = 3:" << endl;
vecpair = equal_range(v.begin(),v.end(),3);
cout << " [vecpair->first, vecpair->second) = ";
copy(vecpair.first, vecpair.second, ostream_iterator<int>(cout," "));
cout << endl << endl;
//binary_search, value = 3
cout << "binary_search function, value = 3:" << endl;
cout << "3 is " << (binary_search(v.begin(),v.end(),3) ? "":"not ") << "in array." << endl;
cout << endl;
//binary_search, value = 6
cout << "binary_search function, value = 6:" << endl;
cout << "6 is " << (binary_search(v.begin(),v.end(),6) ? "":"not ") << "in array." << endl;
cout << endl;
return 0;
}
array:
0 0 0 1 1 1 1 2 2 2 2 3 3 3 4 4 4 5 5 5
lower_bound function, value = 3:
[first, itr) = 0 0 0 1 1 1 1 2 2 2 2
[itr, last) = 3 3 3 4 4 4 5 5 5
upper_bound function, value = 3:
[first, itr) = 0 0 0 1 1 1 1 2 2 2 2 3 3 3
[itr, last) = 4 4 4 5 5 5
equal_range function, value = 3:
[vecpair->first, vecpair->second) = 3 3 3
binary_search function, value = 3:
3 is in array.
binary_search function, value = 6:
6 is not in array.