9.3 Magic Index

A magic index in an arrayA[l…n-l]is defined to be an index such thatA[i] = i. Given a sorted array of distinct integers, write a method to find a magic index, if one exists, in array A.

---

public int findMagicIndex(int[] num) {
	int start = 0, end = num.length - 1;
	while (start <= end) {
		int mid = (start + end) / 2;
		if (num[mid] == mid) {
			return mid;
		}
		if (num[mid] > mid) {
			end = mid - 1;
		} else {
			start = mid + 1;
		}
	}
	return -1;
}

FOLLOW UP
What if the values are not distinct?
当有重复的时候，两边都要比，但是不用比所有的元素，比较巧妙。

public int findMagicIndex(int[] num) {
	return subFind(num, 0, num.length - 1);
}

private int subFind(int[] num, int start, int end) {
	int result = -1;
	if (start > end) {
		return -1;
	}
	int mid = (start + end) / 2;
	if (num[mid] == mid) {
		return mid;
	}
	if (num[mid] > mid) {
		result = subFind(num, start, mid - 1) == -1 ? result = subFind(num, num[mid], end);
	} else {
		result = subFind(num, mid + 1, end) == -1 ? subFind(num, start, num[mid]);
	}
	return result;
}