#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;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgoKdHlwZWRlZiBzdGQ6OnZlY3RvcjxpbnQ+IHZlY3RfdDsKdHlwZWRlZiBzdGQ6OnZlY3RvcjxpbnQ+OjppdGVyYXRvciB2ZWN0X2l0ZXI7Cgp2ZWN0X2l0ZXIgYnNlYXJjaCAodmVjdF90JiB2LCBpbnQgdmFsdWUpCnsKCWF1dG8gbGVmdCAgPSB2LmJlZ2luKCk7CglhdXRvIHJpZ2h0ID0gdi5lbmQoKTsKCXdoaWxlIChsZWZ0ICE9IHJpZ2h0KQoJewoJCWF1dG8gbWlkID0gbGVmdCArIChyaWdodCAtIGxlZnQpIC8gMjsKCQlpZiAoKm1pZCA9PSB2YWx1ZSkKCQkJcmV0dXJuIG1pZDsKCQllbHNlIGlmICh2YWx1ZSA+ICptaWQpCgkJCWxlZnQgPSBtaWQgKyAxOwoJCWVsc2UKCQkJcmlnaHQgPSBtaWQ7Cgl9CglyZXR1cm4gdi5lbmQoKTsKfQoKdmVjdF9pdGVyIHJlY3Vyc2l2ZV9ic2VhcmNoICh2ZWN0X2l0ZXImIGxlZnQsIHZlY3RfaXRlciYgcmlnaHQsIGludCB2YWx1ZSkKewoJaWYgKGxlZnQgIT0gcmlnaHQpCgl7CgkJYXV0byBtaWQgPSBsZWZ0ICsgKHJpZ2h0IC0gbGVmdCkgLyAyOwoJCWlmICgqbWlkID09IHZhbHVlKQoJCQlyZXR1cm4gbWlkOwoJCWVsc2UgaWYgKHZhbHVlID4gKm1pZCkKCQkJcmV0dXJuIHJlY3Vyc2l2ZV9ic2VhcmNoICgrK21pZCwgcmlnaHQsIHZhbHVlKTsKCQllbHNlCgkJCXJldHVybiByZWN1cnNpdmVfYnNlYXJjaCAobGVmdCwgLS1taWQsIHZhbHVlKTsKCX0KCXJldHVybiByaWdodDsKfQoKaW50IG1haW4oKQp7CglzdGQ6OnZlY3RvcjxpbnQ+IHYgPSB7MCwgMSwgMiwgMywgNCwgNSwgNiwgNywgOCwgOX07CgoJc3RkOjpjb3V0IDw8ICpic2VhcmNoKHYsIDcpIDw8IHN0ZDo6ZW5kbDsKCXN0ZDo6Y291dCA8PCAqYnNlYXJjaCh2LCAzKSA8PCBzdGQ6OmVuZGw7CglzdGQ6OmNvdXQgPDwgKmJzZWFyY2godiwgMTEpIDw8IHN0ZDo6ZW5kbDsKCglzdGQ6OmNvdXQgPDwgKnJlY3Vyc2l2ZV9ic2VhcmNoKHYuYmVnaW4oKSwgdi5lbmQoKSwgNykgPDwgc3RkOjplbmRsOwogICAgICAgIHN0ZDo6Y291dCA8PCAqcmVjdXJzaXZlX2JzZWFyY2godi5iZWdpbigpLCB2LmVuZCgpLCAzKSA8PCBzdGQ6OmVuZGw7CiAgICAgICAgc3RkOjpjb3V0IDw8ICpyZWN1cnNpdmVfYnNlYXJjaCh2LmJlZ2luKCksIHYuZW5kKCksIDExKSA8PCBzdGQ6OmVuZGw7Cgp9
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)
^