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: Run This Code

Run This 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...