Binary Search Algorithm STL C++
binary search algorithm stl
The binary search algorithm stl performs a binary search on an ordered sequence beginning at start and ending with end for the value specified by val. It returns true if the val is found and false otherwise. The first version compares the elements in the specified sequence for equality. The second version allows you to specify your own comparison function.
template <class ForwardIterator, class T> bool binary_search ( ForwardIterator first, ForwardIterator last, const T& value ); template <class ForwardIterator, class T, class Compare> bool binary_search ( ForwardIterator first, ForwardIterator last, const T& value, Compare comp );
Implementation of Binary Search Algorithm STL C++
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef int type;
void print(vector <type> vec0) {
vector <type>::iterator it;
for (it = vec0.begin(); it != vec0.end(); it++)
cout << *it << " ";
cout << endl;
}// print
bool my_less(int num1, int num2) {
return (num1 < num2);
}//end of my_less
int main() {
vector<type> vec;
vec.push_back(1);
vec.push_back(20);
vec.push_back(10);
vec.push_back(36);
vec.push_back(63);
vec.push_back(5);
sort(vec.begin(), vec.end());
//print(vec);
cout << "searching for a 20"<<endl;
if (binary_search (vec.begin(), vec.end(), 20))
cout << "found";
else cout << "not found";
return 0;
}//end of main
Iterators C++
The STL implements five different types of iterators. These are input iterators (that can only be used to read a sequence of values), output iterators (that can only be used to write a sequence of values), forward iterators (that can be read, written to, and move forward), bidirectional iterators (that are like forward iterators, but can also move backwards) and random access iterators (that can move freely any number of steps in one operation).
It is possible to have bidirectional iterators act like random access iterators, as moving forward ten steps could be done by simply moving forward a step at a time a total of ten times. However, having distinct random access iterators offers efficiency advantages. For example, a vector would have a random access iterator, but a list only a bidirectional iterator.
Iterators are the major feature that allow the generality of the STL. For example, an algorithm to reverse a sequence can be implemented using bidirectional iterators, and then the same implementation can be used on lists, vectors User-created containers only have to provide an iterator that implements one of the five standard iterator interfaces, and all the algorithms provided in the STL can be used on the container.
