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

- If end < start then
- return – 1

- Compute middleIndex = (start + end ) / 2
- If
`middleIndex == A[middleIndex]`

then- return middleIndex

- Compute leftIndex = min(middleIndex -1, A[middleIndex])
- Recursively Call for leftPortion with start and leftIndex
- If
`left < 0`

then- return left

- Compute
`rightIndex = max (middleIndex +1, A[middleIndex ])`

- Recursively call for rightPortion with rightIndex and end
- 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