MagicIndex.java

//http://coolcodebro.blogspot.com/2012/12/find-index-in-array-such-that-ai-i.html

void run() {
	int[] arr = {-3, -1, 0, 1, 2, 4, 6, 9};
	System.out.printf("Magic index: %d%n", getMagicIndex(arr));
}

int getMagicIndex(int[] arr) {
	if(arr.length == 0) 
		return -1;
	
	return getMagicIndex(arr, 0, arr.length-1);
}

//Binary search ftw!
int getMagicIndex(int[] arr, int low, int high) {
	if(low > high)
		return -1;
	
	int mid = (high + low) / 2;
	
	if(arr[mid] < mid)
		return getMagicIndex(arr, mid+1, high);
	if(arr[mid] > mid)
		return getMagicIndex(arr, low, mid-1);
	
	return mid;
}