# [CC150v5] 9.3 Find Magic Index

### 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);
}
}
}
``````