#include <iostream>

using namespace std;

//returns the index i such that array[i] = i; 
//if no such element exists, return -1
int getMagicIndex(int array[], int low, int high)
{
	if( low > high )
		return -1;

	int mid = low + (high-low)/2;
	cout << "check" << endl;
	
	if ( array[mid] == mid )
		return mid;
	if( mid > array[mid] )
		return getMagicIndex(array, mid+1, high);
	else
		return getMagicIndex(array, low, mid-1);
}

int main()
{
	int array[] = {-20, -10, 0, 5, 10, 15, 20, 25, 30, 35, 40};
	int magicInd = getMagicIndex(array, 0, 11);
	cout << magicInd << endl;
	return 0;
}