Matsushita's Blog

Find a Magic Index from Sorted Array


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.


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.

Binary Search by While Loop