#include <iostream>
#include <ctime>
#include <cstdlib>
#include <algorithm>
using namespace std;

void populate(int x[], int num){
	for(int i = 0; i < num; i++)
		x[i] = rand()%(3*num) + 1;
	cout << " numbers are " << endl;

	// stl version from <algorithm>
	sort(x, x+num);
	for(int i = 0; i < num; i++)
		cout << i << " " << x[i] << endl;
}

int ken_binary_search(int *lo, int *hi, int target){
	if(lo > hi)return 0;

	// amount of data will be approximately 1/2 of
	// last amount of data or O(log(n)) performance.
	int delta = hi - lo;
	cout << " searching " << delta << " numbers." << endl;
	int *mid = lo + delta/2;
	if(*mid == target) return 1;
	else if(target < *mid) return ken_binary_search(lo, mid-1,target);
	else return  ken_binary_search(mid+1, hi, target);
}

void main(){
	//srand(time(0));
	srand(99);
	bool flag = true;
	while(flag){
		cout << "how many numbers?" << endl;
		int na = 0;
		cin >> na;
		int *a = new int[na];
		populate(a, na);
		cout << "What are we looking for?" << endl;
		int number = 0;
		cin >> number;

		// stl version from <algorithm>
		//cout << binary_search(a, a+na, number)<< endl;
		cout << ken_binary_search(a,a+na,number) << endl;
		delete [] a;
		cout << "continue ? (1/0)" << endl;
		cin >> flag;
	}
}