Magic Index

Lessons Learned: Arrays, binary search, recursion

Question 5: Magic Index: A magic index is an index in an array such that array[i] = i. Given an array of sorted numbers, find the magic number.

A quick, brute force would involve iterating through the array, and finding the array position such that array[i] = i. But we can come up with a faster position, especially since the prompt says that the array is sorted.

Let’s take advantage of the fact that the array is sorted to write a quicker solution. Let’s look at the middle index in the array, call it mid, and compare it to array[mid]:

Case 1: array[mid] = mid. We’re done as this is the magic number. We return mid.

Case 2: array[mid] > mid. Because the array is sorted, we can now infer that the magic index has to be to the left of this number.

How do we know this? Let’s take this array: [-2, 0, 1, 4, 5]

And we are looking at position 3 (value 4), we know that the magic index can’t exist to the right of this position because we’ve already reached a value that is larger than the index. Since values only get larger as we move to the right, we’ll never reach a case where array[mid] = mid. We will look to the left of this array to find the magic number.

Case 3: array[mid] < mid. Because the array is sorted, we can now infer that the magic index has to be to the right of this position (using the same above explanation).

This above approach with three cases is an example of binary search. Binary search is a searching technique in which you search for numbers by looking at half of the list repeatedly until you reach the number you are searching.

As we learned in the last post regarding recursion, we can use the 3-case approach recursively on halves of the array until we find the desired magic index. Below is the code writeup of the solution:

We’re done!

More Questions:

Programming GIFs - Get the best GIF on GIPHY