#include <iostream>
#include <algorithm>

using namespace std;



/*
Implemented from psuedocode at wikipedia.  
See: http://en.wikipedia.org/wiki/Binary_search
*/
int binarySearch(int arr[], int n, int value)
{
  int low = 0;
  int high = n-1;
  
  while (low <= high) {
	int mid = (low + high) / 2;   
	
	if (arr[mid] > value) {
	  high = mid - 1;
	} else if (arr[mid] < value) {
	  low = mid + 1;
	} else {
	  return mid; // found
	}
  }
  
  return -1;
}

int main()
{
  cout << endl;

  const int N = 25;
  int arr[N] = {442, 321, 171, 73, 941, 635, 706, 146, 437, 
				360, 111, 551, 562, 958, 586, 229, 76, 145, 
				572, 628, 539, 677, 567, 972, 878 };
  
  // first sort the numbers.
  sort(arr, arr+N);

  
  // Now find some numbers
  int x = 73;
  cout << x << " is at position " << binarySearch(arr,N, x) << endl;

  x = 567;
  cout << x << " is at position " << binarySearch(arr,N, x) << endl;

  x = 972;
  cout << x << " is at position " << binarySearch(arr,N, x) << endl;

  cout << endl;

  return 0;
}