fork download

copy

#include <iostream>
#include <vector>
 
typedef std::vector<int> vect_t;
typedef std::vector<int>::iterator vect_iter;
 
vect_iter bsearch (vect_t& v, int value)
{
	auto left  = v.begin();
	auto right = v.end();
	while (left != right)
	{
		auto mid = left + (right - left) / 2;
		if (*mid == value)
			return mid;
		else if (value > *mid)
			left = mid + 1;
		else
			right = mid;
	}
	return v.end();
}
 
vect_iter recursive_bsearch (vect_iter& left, vect_iter& right, int value)
{
	if (left != right)
	{
		auto mid = left + (right - left) / 2;
		if (*mid == value)
			return mid;
		else if (value > *mid)
			return recursive_bsearch (++mid, right, value);
		else
			return recursive_bsearch (left, --mid, value);
	}
	return right;
}
 
int main()
{
	std::vector<int> v = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
 
	std::cout << *bsearch(v, 7) << std::endl;
	std::cout << *bsearch(v, 3) << std::endl;
	std::cout << *bsearch(v, 11) << std::endl;
 
	std::cout << *recursive_bsearch(v.begin(), v.end(), 7) << std::endl;
        std::cout << *recursive_bsearch(v.begin(), v.end(), 3) << std::endl;
        std::cout << *recursive_bsearch(v.begin(), v.end(), 11) << std::endl;
 
}

prog.cpp: In function 'int main()':
prog.cpp:47:41: error: invalid initialization of non-const reference of type 'vect_iter& {aka __gnu_cxx::__normal_iterator<int*, std::vector<int> >&}' from an rvalue of type 'std::vector<int>::iterator {aka __gnu_cxx::__normal_iterator<int*, std::vector<int> >}'
  std::cout << *recursive_bsearch(v.begin(), v.end(), 7) << std::endl;
                                         ^
prog.cpp:24:11: note:   initializing argument 1 of 'vect_iter recursive_bsearch(vect_iter&, vect_iter&, int)'
 vect_iter recursive_bsearch (vect_iter& left, vect_iter& right, int value)
           ^
prog.cpp:48:48: error: invalid initialization of non-const reference of type 'vect_iter& {aka __gnu_cxx::__normal_iterator<int*, std::vector<int> >&}' from an rvalue of type 'std::vector<int>::iterator {aka __gnu_cxx::__normal_iterator<int*, std::vector<int> >}'
         std::cout << *recursive_bsearch(v.begin(), v.end(), 3) << std::endl;
                                                ^
prog.cpp:24:11: note:   initializing argument 1 of 'vect_iter recursive_bsearch(vect_iter&, vect_iter&, int)'
 vect_iter recursive_bsearch (vect_iter& left, vect_iter& right, int value)
           ^
prog.cpp:49:48: error: invalid initialization of non-const reference of type 'vect_iter& {aka __gnu_cxx::__normal_iterator<int*, std::vector<int> >&}' from an rvalue of type 'std::vector<int>::iterator {aka __gnu_cxx::__normal_iterator<int*, std::vector<int> >}'
         std::cout << *recursive_bsearch(v.begin(), v.end(), 11) << std::endl;
                                                ^
prog.cpp:24:11: note:   initializing argument 1 of 'vect_iter recursive_bsearch(vect_iter&, vect_iter&, int)'
 vect_iter recursive_bsearch (vect_iter& left, vect_iter& right, int value)
           ^

Standard output is empty