# Magic Index

### 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
```
Author: