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

CC150-9.3.java

package POJ;

public class Main{
 
	/**
	 * 
	 * 9.3 A magic index in an array A[1.. .n-1] is defined to be an index such that A =i. Given a sorted 
	 * array of distinct integers, write a method to find a magic index, if one exists, in array A.
	 * FOLLOW UP
	 * What if the values are not distinct?
	 * 
	 */

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

CC150-9.3FollowUp.java

package POJ;

public class Main{
 
	/**
	 * 
	 * 9.3 A magic index in an array A[1.. .n-1] is defined to be an index such that A =i. Given a sorted 
	 * array of distinct integers, write a method to find a magic index, if one exists, in array A.
	 * FOLLOW UP
	 * What if the values are not distinct?
	 * 
	 * 
	 */
	public static void main(String[] args) {
		Main so = new Main();
	}

	public int getMagicIndexFollowup(int[] array, int start, int end) {
		if (end < start || end > array.length - 1 || start < 0)
			return -1;
		int midIndex = (end - start) / 2 + start;
		int midValue = array[midIndex];
		if (midIndex == midValue)
			return midIndex;
		// search left
		int leftIndex = Math.min(midIndex - 1, midValue);
		int left = getMagicIndexFollowup(array, start, leftIndex);
		if (left >= 0)
			return left;
		// search right
		int rightIndex = Math.max(midIndex + 1, midValue);
		int right = getMagicIndexFollowup(array, rightIndex, end);
		return right;
	}
}