Be the first user to complete this post

Add to List 
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:
The naive approach is to do the linear scan and find the magic index in O(n).
A 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 a 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 a 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
Also Read: