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:


Output:

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 :
    array={1,2,3,3,4,5,6,7,8,9,10}
    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?

  • http://tkachuko.info Oleksii Tkachuk

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

%d bloggers like this: