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.

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();
}

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]);

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();
}