**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:**

**Output**:

Magic index 4

__________________________________________________

**Top Companies Interview Questions..-**

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.

__________________________________________________

### Like this:

Like Loading...

*Related*