#include <iostream>
#include <typeinfo>
#include <iterator>
#include <vector>
#include <list>

template <typename T, typename V>
T binary_search(T left, T right, V find)
{
	if(left > right){
		std::swap(left,right);
	}

	if (typeid(*left) == typeid(V)){
		
		auto distance = std::distance(left, right);
		T current = std::next(left,distance/2);
		
		do{
			if(*current == find)
			
			else if (*current > find){
				distance = distance/2;
				current = std::prev(current,distance);
			}
			
			else if (*current < find){
				distance = distance/2;
				current = std::next(current,distance);
			}
			
			else return right;
			
		}while(distance>0);
	}
	return right;
}

int main() {
	
	std::vector<int> v = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20};
	std::list<int> l = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20};
	
	auto vi = binary_search(l.begin(), l.end(), 12);
	int b = *vi;
	std::cout << b <<' ';//<< ' ' << std::distance(v.begin(),vi);
	
	return 0;
}