/*
   show binary search vs find
*/
#include <iostream>
#include <vector>  
#include <algorithm> // get sort, find, binary_search
#include <time.h> // for a seed
#include <cmath>  // random number generator
using namespace std;

void main(){

	srand(time(0)); // randomize random number sequence

	// now use a vector
	vector<int> v(20); // declare a vector

	// randomly load the vector with data
	for(int i = 0; i < 20; i++)
		v[i]= rand()%1000;

	// use find on the unsorted data
	// O(n) effort for each find
	vector<int>::iterator it;
	for(int i = 0; i < 1000; i++){
		it = find(v.begin(), v.end(), i);
		if(it != v.end())
           cout<< " found " << *it << endl;
	}

	// tie vector to sort via begin and end iterators
	sort(v.begin(), v.end());

	// use binary search on sorted data 
	// (must sort before binary_search try commenting out sort)
	// O(log(n)) effort
	for(int i = 0; i < 1000; i++){
		if(binary_search(v.begin(), v.end(), i))
           cout<< " found via binary " << i << endl;
		
	}
	
	// declare an iterator - in this case, the container
	// vector defines the iterator
	vector<int>::iterator iv;

    // iterate through the vector container
	for(iv = v.begin(); iv != v.end(); iv++)
		cout << *iv << endl; // use dereference operator overload of iterator

}