Magic Index — Find Index In Sorted Array Such That A[i] = i.

Objec­tive: Given a sorted array of dis­tinct inte­gers, 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.

Exam­ple :

int[] A = { -1, 0, 1, 2, 4, 10 };

Magic index or fixed point is : 4

Approach:

Naive approach is to do the lin­ear scan and find the magic index in O(n).

Bet­ter solu­tion would Mod­ify the Binary SearchTime Com­plex­ity 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 recur­sive 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 recur­sive call to search(A, start, mid — 1).

Code:


Out­put:

Magic index 4

You may also like...

  • Kamal

    in the exam­ple you have given, the array is not sorted

    • tuto­ri­al­hori­zon

      Thanks kamal for point­ing it out, cor­rected it.

  • Sai Yashod­har Vinay

    this algo­rithm is wrong

    Here the counter exam­ple :
    array={1,2,3,3,4,5,6,7,8,9,10}
    will return –1 not 3
    Please check it out

    • tuto­ri­al­hori­zon

      The pro­gram is works for dis­tinct inte­gers, My bad the objec­tive of the prob­lem was con­fus­ing, i have cor­rected it. Thanks for find­ing it out.

  • Aish­warya Parasuram

    Is there a sim­i­lar binary search method for arrays with repeated ele­ments or is lin­ear scan the only way?

  • http://tkachuko.info Olek­sii Tkachuk

    Thanks for post! Did you look into the case when ele­ments are not distinct?