# 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 SearchTime 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:

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

 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

view raw

MagicIndex.java

hosted with ❤ by GitHub

Output:

```Magic index 4
```