#include <iostream>
#include <vector>

using namespace std;

bool recherche(const vector<int> &vec, int x) {
	for(int i = 0; i < vec.size(); ++i)
	{
		if(vec[i] == x)
			return true;
		if(vec[i] > x)
			return false;
	}

	return false;
}

bool recherche3(const vector<int> &vec, int x) {
	int debut = 0, fin = vec.size() - 1;
	while(debut <= fin) {
		int mil = (debut + fin)/2;

		cout << "debut = " << debut << endl;
		cout << "fin = " << fin << endl;
		cout << "mil = " << mil << endl;

		if(x == vec.at(mil))
			return true;
		if(x < vec.at(mil))
			fin = mil - 1;
		else // x > vec.at(mil)
			debut = mil + 1;
	}
	return false;
}

int main()
{
	cout << recherche3({1,2,3,4}, 5) << endl;
//	cout << recherche3({1,2,3,4}, 4) << endl;
//	cout << recherche3({1,2,3,4}, 0) << endl;
//	cout << recherche3({1,2,3,4}, 5) << endl;
//	cout << recherche3({1,2,4}, 3) << endl;
}