Finding the magic index in array, A

Problem

A magic index in an array A [0. . .n-1] 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?

Answer

This is another question I found interesting in the Cracking coding interview book.

Brute-force approach, $O(N)$

The simplest way to solve this problem is to scan the array, A from A[0] to A[N-1] looking for the index, i where A[i] = i.

However, this wouldn't be the answer to this question. This means the question is asking for a faster algorithm than $O(N)$. Possible $O(\log N)$ ?

Recursive Binary search approach, $O( \log N)$

Let's draw out the example array with the magic index at 3 with the size of 5. It would be like the below:

Figure 1. Example input

On the left size of the magic index, A[i] > i holds while i > A[i] holds on the right side of the magic index.

This gives enough information to perform the binary search following the algorithm below

Given, chosen half, h,

case 1) if A[h] == h, found the magic index

case 2) if A[h] > i, search the right size of index, h

case 3) if A[h] < i. search the right size of index, h

This algorithm will run in $O(\log N)$

If the values are not distinct, binary search will not work since both left and right sides of the magic index can have integers either greater than the index or less than the index.

Therefore, only linear scanning will work, which results in $O(N)$ time complexity
Here is the complete answer to the first part of the question.

Update (05.06.2016):

Initially, I thought only linear scanning will work if there are duplicate keys. However, I later realized that we can still perform the recursive search, which is marginally better than the linear scanning depending on the combination of the integers in the array.

Take the look at Figure 2, which presents array A, with duplicate integers.

Figure 2. For example case of duplicate integers, there are two magic indexes

There are three indexes in 2, and 8th in the array. However, we can no longer use the rules to determine whether to search the left or right half of the array anymore since the rules applied for the previous case do not hold anymore.

It is a major setback. However, there is the still a room for improvement. We should now search both sides of the array each time but we can still reduce the scope to search based on the following rules.

Given start, the starting position, and end the end position, the h, index splitting the array in half and A[h] the value in that position,

Rule 1) For the left side of the array, we now know that index h can't be the magic index anymore.
In choosing the new end index for search, we can choose the minimum of h-1 and A[h].
Therefore, we search between start and Min(h-1, A[h])

 Rule 2) For the right side of the array, we also know that index h can't be the magic index anymore.
In choosing the new start index for search, we can choose the maximum of h-1 and A[h].
Therefore, we search between Max(h-1, A[h]) and end

UPDATE(2022-06-24): This algorithm can't work if the negative values are allowed in the array. This is only valid if only non-negative values are in the array.

I would say the expected running time is faster than $O(N)$ since it is not guaranteed that we can reduce the search space each time considerably.
However, it will be faster than the linear search in practice.

The following code is modified to apply the two rules explained above.

	#include<iostream>
	#include<vector>
	using namespace std;
	int find_magic_index(vector<int>&list, int s, int e)
	{
	if (s>e || s < 0 || s>= list.size() || e < 0 || e >= list.size())
	return INT_MIN;
	int h = s + (e-s)/2;
	if (h == list[h])
	return h;
	int l_end = (list[h]>h)? h-1 : list[h];
	int found = find_magic_index(list, s, l_end);
	if (found != INT_MIN)
	return found;
	int r_start = (list[h]>h)? list[h] : h+1;
	found = find_magic_index(list, r_start, e);
	return found;
	}
	int main()
	{
	vector<int> list;
	list.push_back(1);
	list.push_back(2);
	list.push_back(3);
	list.push_back(3);
	list.push_back(3);
	list.push_back(4);
	list.push_back(5);
	list.push_back(9);
	list.push_back(10);
	list.push_back(10);
	list.push_back(11);
	cout<<"magic index with duplicates = " << find_magic_index(list, 0, list.size()-1)<<endl;
	vector<int> list2;
	list2.push_back(-10);
	list2.push_back(-5);
	list2.push_back(1);
	list2.push_back(1);
	list2.push_back(1);
	list2.push_back(4);
	list2.push_back(5);
	list2.push_back(9);
	list2.push_back(10);
	list2.push_back(10);
	list2.push_back(10);
	cout<<"magic index with duplicates = " << find_magic_index(list2, 0, list2.size()-1)<<endl;
	return 1;
	}

view raw find_magic_index_with_duplicate.cpp hosted with ❤ by GitHub

Practice statistics
19:23: to write up the code
08:48: to realize the second question is for $O(N)$

** April 28 2019: Tried again in Python. Here is a solution in Python

	'''
	A magic index in an array A [0. . .n-1] 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.
	first question:
	21 mins: to write up the complete code
	FOLLOW UP
	What if the values are not distinct?
	5 mins: to write up the complete code searching both side.
	'''
	class FindMacgicIndex:
	def find_index(self, input):
	return self.search(0, len(input)-1, input)
	def search(self, start, end, input):
	if start > end :
	return None
	half = start + (end - start)/2
	if input[half] == half:
	return half
	elif input[half] > half:
	return self.search(start, half - 1, input)
	#input[half] < half
	return self.search(half + 1, end, input)
	f = FindMacgicIndex()
	input = [ -1, 0, 2, 3, 4, 5, 6, 8, 9, 11]
	print("magic index for {} is {}".format(input, f.find_index(input)))
	input = [ -1, 0, 2, 3, 4, 5, 7, 8, 9, 11]
	print("magic index for {} is {}".format(input, f.find_index(input)))
	#if the value is not distinct, we can determine which half to choose. Search both in that case.
	# It is O(N) algorithm but it will be faster in practice
	class FindMacgicIndexNonDistinct:
	def find_index(self, input):
	return self.search(0, len(input)-1, input)
	def search(self, start, end, input):
	if start > end :
	return None
	half = start + (end - start)/2
	if input[half] == half:
	return half
	#search left first
	found = self.search(start, half - 1, input)
	if found == None:
	#now search right half
	found = self.search(half + 1, end, input)
	return found
	f2 = FindMacgicIndexNonDistinct()
	input = [ 1, 3, 3, 3, 5, 7, 8, 9, 9, 11]
	print("magic index for {} is {}".format(input, f2.find_index(input)))
	input = [ 1, 3, 4, 5, 5, 6, 7, 9, 10, 11]
	print("magic index for {} is {}".format(input, f2.find_index(input)))

view raw find_magic_index.py hosted with ❤ by GitHub

Practice statistics

21 mins: to write up the code
5 mins to write up the answer to the second question is for $O(N)$

UPDATE(2022-06-24): Solved the problem again with the binary search with the distinct flag as a parameter to denote the condition for the duplicate values in the array.

	# code
	def search(input, start, end):
	if start > end:
	return None
	half = (start + end) //2
	if input[half] == half:
	return half
	elif input[half] > half: # search left
	return search(input, start, half -1)
	else: # search right
	return search(input, half + 1, end)
	def search_duplicate(input, start, end):
	if start > end:
	return None
	half = (start + end) //2
	if input[half] == half:
	return half
	# it is unclear whether to search left or right. So search both.
	found = search_duplicate(input, start, half - 1)
	if found == None:
	return search_duplicate(input, half + 1, end)
	return found
	def find_magic_index(input, distinct=True):
	return search(input, 0, len(input) - 1) if distinct == True else search_duplicate(input, 0, len(input) - 1)
	# test
	input = [-1,0,2,4,5,7]
	magic_index = find_magic_index(input)
	print("magic index for {} is {} and value = {}".format(input, magic_index, input[magic_index]))
	input = [1,1,1,3,5,7]
	magic_index = find_magic_index(input, distinct=False)
	print("magic index for {} is {} and value = {}".format(input, magic_index, input[magic_index]))
	input = [-1,-1,-1,3,5,7]
	magic_index = find_magic_index(input, distinct=False)
	print("magic index for {} is {} and value = {}".format(input, magic_index, input[magic_index]))

view raw find_magic_index.py hosted with ❤ by GitHub

10:22: to write up the code

03:58: to review the code.