Magic Index

A magic index in an array A[0….N-1] is defined to an index such that A[i] = i. Given a sorted array of distinct integers. Find that index if it exists in array and values of array are not distinct.

Solution:

• Similar to binary search but complexity increased when it mentioned that array has duplicate element.
• So, find middleIndex = (start + end) /2
• If middleIndex == A[middleIndex] then return middleIndex
• Else search left portion of array by computing left Index till leftIndex >=0
  • leftIndex = min(middleIndex – 1, A[middleIndex])
• Else search right portion of array by computing right Index till right <= end
  • rightIndex = max(middleIndex + 1, A[middleIndex])

Algorithm:

1. If end < start then
   1. return – 1
2. Compute middleIndex = (start + end ) / 2
3. If middleIndex == A[middleIndex] then
   1. return middleIndex
4. Compute leftIndex = min(middleIndex -1, A[middleIndex])
5. Recursively Call for leftPortion with start and leftIndex
6. If left < 0 then
   1. return left
7. Compute rightIndex = max (middleIndex +1, A[middleIndex ])
8. Recursively call for rightPortion with rightIndex and end
9. return right

Latest Source Code:
Github: MagicIndex.java

Output:

Array: [3, 8, 10, 17, 18, 30, 100] -> Magic Index : -1
Array: [-2, -1, 2, 2, 2, 6, 7] -> Magic Index : 2
Array: [-3, -2, -1, 0, 4, 6, 7, 10] -> Magic Index : 4