# Magic Index

**8.3 Magic Index:** A magic index in an array A \[e ... 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?

**The idea:** Use binary search to help guide us to the magic index. Consider, for example, the array

```
# 0 1 2 3 4 5 6 7 8 9 10
t1 = [-40,-20, -1, 1, 2, 3, 5, 7, 9, 12, 13]
```

Say we land at index 3. Because all the elements are distinct, we know that `A[i+1] > A[i]`. Because the index 3 is greater than in the value at 3, which is 1, we know that the value has to catch up so it must exist in the right part of the array. The opposite is true for the left side.

```cpp
int binary_search(vector<int> &nums, int low, int high) {
    if (high < low)
        return -1;

    int mid = low + ((high - low) / 2);
    if (nums.at(mid) == mid) return mid;
    else if (nums.at(mid) < mid)
        binary_search(nums, mid + 1, high);
    else
        binary_search(nums, low, mid - 1);
    }

int magicIndex(vector<int> &nums) {
    return binary_search(nums, 0, nums.size() - 1);
}


int main()
{
    vector<int> nums = {-40,-20 -1, 1, 2, 3, 5,7, 9, 12, 13};
    cout << magicIndex(nums) << endl;
    pause();

    nums = { 0,1, 3,4,5,6 };
    cout << magicIndex(nums) << endl;
    pause();

    nums = { -1010, -10, 2, 4, 5, };
    cout << magicIndex(nums) << endl;
    pause();
}
```

```python
def find_magic_index(ar):
    def __find_magic_index(left, right):
        if left <= right:
            mid = int(left + (right - left) / 2)
        if mid == ar[mid]:
            return mid
        elif mid < ar[mid]:
            return __find_magic_index(left, mid - 1)
        else:
            return __find_magic_index(mid + 1, right)
        else:
            return -1
    return __find_magic_index(0, len(ar) - 1)
```

We can show that if we have distinct elements, then our algorithm could fail. For example below, algorithm would search right when reach observing that A\[4] < 4, when this is not the case.

```
  0  1 2 3 4 5 6 7  8
-10,-5,2,2,2,2,2,2, 9
```

With this example, we can easily should the searching left or searching right are valid options.

So to formulate the upper bound on the left hand side:

```
int index_left = min(cur_index - 1, cur_index - abs(A[cur_index] - cur_index));
```

Which if you do the math, simplifies to:

```
int index_left = min(cur_index - 1, A[cur_index]);
```

```cpp
int binary_search(vector<int> &nums, int low, int high) {
    if (high < low)
        return -1;

    int mid = low + ((high - low) / 2);
    if (nums.at(mid) == mid) return mid;

    // left
    int left_i = min(mid - 1, nums.at(mid));
    int left = binary_search(nums, 0, left_i);
    if (left >= 0) return left;

    // right
    int right_i = max(mid + 1, nums.at(mid));
    int right = binary_search(nums, mid + 1, right_i);

    return right;
}

int magicIndex(vector<int> &nums) {
    return binary_search(nums, 0, nums.size() - 1);
}


int main()
{
    vector<int> nums = { -10,-5,2,2,2,3,4,7,9,12,13 };
    cout << magicIndex(nums) << endl;
    pause();
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://maksimdan.gitbook.io/interview-practice-problems/coding_practice_questions/recursion_and_dynamic_programming/magic-index.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.