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

in the example you have given, the array is not sorted

Thanks kamal for pointing it out, corrected it.

this algorithm is wrong

Here the counter example :

array={1,2,3,3,4,5,6,7,8,9,10}

will return -1 not 3

Please check it out

The program is works for distinct integers, My bad the objective of the problem was confusing, i have corrected it. Thanks for finding it out.

Is there a similar binary search method for arrays with repeated elements or is linear scan the only way?

Thanks for post! Did you look into the case when elements are not distinct?