//Graham Pocta
//Binary Search
#include <iostream>
#include <stdio.h>

using namespace std;

int main (void) {
	
	int ARRAY_SIZE;
    int searchNumber;	
	
	printf("How many values are going to be in the array?");
	cin>>ARRAY_SIZE;
	
	int array[ARRAY_SIZE];
	
	printf("Please input the numbers, separated by spaces. ");
	
	for(int i=0;i<ARRAY_SIZE;i++)
	{
		cin>>array[i];
	}

	printf("For what number would you like to search?");
    cin>>searchNumber;
    
 	int middle, found=0, first=0, last=ARRAY_SIZE-1;
 	
	while((first <= last) && !found) {

		middle = (first + last) / 2;

		if (array[middle] == searchNumber) 
			found = 1; 
		else if (array[middle] < searchNumber) 
			first = middle+1;
		else 
			last = middle - 1; 
	}
	
	if (found) 
		cout<<"The position is "<<middle<<endl; 
	else 
		cout<<"The position is -1"<<endl; 
} // main