Magic Index - Find Index In Sorted Array Such That A[i] = i.

Objective: Given a sorted array of distinct integers, Find the Magic index or Fixed point in the array.

Magic Index or Fixed Point: Magic index or a Fixed point in an array is an index i in the array such that A[i] = i.

Example :

int[] A = { -1, 0, 1, 2, 4, 10 };

Magic index or fixed point is : 4

Approach:

Naive approach is to do the linear scan and find the magic index in O(n).

Better solution would Modify the Binary Search – Time Complexity O(logN).

Check mid = (start+end)/2, with A[mid], check if A[mid] = mid. if yes then return mid.
If mid>A[mid] means fixed point might be on the right half of the array, make a recursive call to search(A, mid + 1, end).
If mid<A[mid] means fixed point might be on the left half of the array, make a recursive call to search(A, start, mid – 1).

Code:

	public class MagicIndex {
	// perform modified binary search
	public int search(int[] A, int start, int end) {
	if (start <= end) {
	int mid = (start + end) / 2;
	if (mid == A[mid]) // check for magic index.
	return mid;
	if (mid > A[mid]) { // If mid>A[mid] means fixed point might be on
	// the right half of the array
	return search(A, mid + 1, end);
	} else {// If mid<A[mid] means fixed point might be on
	// the left half of the array
	return search(A, start, mid – 1);
	}
	}
	return –1;
	}

	public static void main(String[] args) {
	// TODO Auto-generated method stub
	int[] A = { –1, 0, 1, 2, 4, 10 };
	MagicIndex m = new MagicIndex();
	System.out.println("Magic index " + m.search(A, 0, A.length – 1));
	}

	}

Output:

Magic index 4

Magic Index – Find Index In Sorted Array Such That A[i] = i.