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


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).



Magic index 4

Top Companies Interview Questions..-

Google Microsoft Amazon Facebook more..

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

You may also like...

  • Kamal

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

    • tutorialhorizon

      Thanks kamal for pointing it out, corrected it.

  • Sai Yashodhar Vinay

    this algorithm is wrong

    Here the counter example :
    will return -1 not 3
    Please check it out

    • tutorialhorizon

      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.

  • Aishwarya Parasuram

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

  • Oleksii Tkachuk

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

%d bloggers like this: