Find a Magic Index from Sorted Array
Problem
A magic index in an array A[] is defined to be an index such that A[i] = i. Given a sorted array of distinct integers, write a method to find a magic index, if one exists, in array A.
FOLLOW UP
What if the values are not distinct?
How to Solve
Of course, this problem can be solve by brute force. the time complexity is 0(N) time. But we can solve it more efficient. The point of this problem is that the given array is sorted. So we can use Binary Search. The time complexity of binary search is O(log N).
Solving by Binary Search
The implementation of binary search is that we keep the range of array and we cut the range in half by the middle of the range.
Follow Up
What if the values are not distinct? In this case, we have to search the both range left and right like this.
