Question 1

A magic index in an array A[l.. .n-l] is defined to be an index such that A[i] = i.

Given a sorted array of distinct integers, write a method to find a magic index, if one exists, in array A.

Question 2

FOLLOW UP: What if the values are not distinct?

Solution

This is a difficult binary search question!

Question 1 is slightly easier: we simplyl use binary search, and we are able to discard half of the array each time.

  1. if (array[mid] > mid), then we discard the right half.
  2. if (array[mid] < mid), then we discard the left half.

Question 2 is difficult. We cannot discard half of the input any more. Instead, we discard a range between (mid) and (array[mid]). Then check left and right part seperately.

So, I wrote the following code:

int mid = left + (right - left) / 2;
if (array[mid] == mid) {
	return mid;
} else {
	int smaller = Math.min(array[mid], mid);
	int larger = Math.max(array[mid], mid);
	int leftResult = helper(array, left, smaller);
	if (leftResult != -1) {
		return leftResult;
	} else {
		return helper(array, larger, right);
	}
}

This becomes an endless loop. We did not discard point ‘mid’ in the code above. The correct code is posted below.

Code

code for non-duplicate input

public static int myAnswerNonDup(int[] array) {
	int len = array.length;
	return helper(array, 0, len - 1);
}

public static int helper(int[] array, int left, int right) {
	if (right < left) {
		return -1;
	}
	int mid = left + (right - left) / 2;
	if (array[mid] == mid) {
		return mid;
	} else if (array[mid] < mid) {
		// discard all element to the left of array[mid]
		return helper(array, mid + 1, right);
	} else {
		return helper(array, left, mid - 1);
	}
}

code for have-duplicate input

public static int myAnswerWithDup(int[] array) {
	int len = array.length;
	return helper(array, 0, len - 1);
}

public static int helper(int[] array, int left, int right) {
	if (right < left) {
		return -1;
	}
	int mid = left + (right - left) / 2;
	if (array[mid] == mid) {
		return mid;
	} else {
		int smaller = 0;
		int larger = 0;
		if (array[mid] < mid) {
			smaller = array[mid];
			larger = mid + 1;
		} else if (array[mid] > mid) {
			smaller = mid - 1;
			larger = array[mid];
		}
		int leftResult = helper(array, left, smaller);
		if (leftResult != -1) {
			return leftResult;
		} else {
			return helper(array, larger, right);
		}
	}
}