Massive Algorithms: [CareerCup] 9.3 Magic Index 魔法序号 - Grandyang

[CareerCup] 9.3 Magic Index 魔法序号 - Grandyang - 博客园
9.3 A magic index in an array A[0.. .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?

这道题定义了一个魔法序号，就是一个数组的序号等于该位置的值的时候，这个序号就是魔法序号，给了我们一个有序数组，让我们来找魔法序号。这里brute force的方法就不提了，因为没啥考察的目的，对于高效的查找方法我们就要首先考虑二分搜索法，首先我们来看这种方法，没啥特别的地方，套用一般的二分查找法的格式即可

    int getMagicIdx(vector<int> &nums) {
        int left = 0, right = nums.size() - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] == mid) return mid;
            else if (nums[mid] > mid) right = mid - 1;
            else left = mid + 1;
        }
        return -1;
    }

这道题的Follow up是说如果数组由重复项怎么处理，那么传统的二分搜索法就会失效，因为下列这种情况可能存在：

-10	-5	2	2	2	3	4	7	9	12	13
0	1	2	3	4	5	6	7	8	9	10

这种情况符合题意，但是左右两边都会出现魔法序号，所以二分查找法会失效。那么我们难道又要用地毯式搜索了么，其实也不必，我们可以用一种类似于二分搜索法的递归方法来解决问题，就拿上面那个例子来说，第一次找到比较完中间点后，由于左右两边都会出现答案，所以我们左右半段要分别递归一下，这里我们可以加一个trick来优化算法，比如要递归左半段时，那么新的右边界就可以设为min(mid - 1, nums[mid])，同理递归右半段时，左边界可以设为max(mid + 1, nums[mid])。还有个小trick，就是如果左半段搜到了答案，那么直接返回即可，不用再搜右半段，因为题目让我们找一个就行了，没说要找出所有的Magic index

    int getMagicIdx(vector<int> &nums) {
        return getMagicIdxDFS(nums, 0, nums.size() - 1);
    }
    int getMagicIdxDFS(vector<int> &nums, int start, int end) {
        if (end < start) return -1;
        int mid = (start + end) / 2;
        if (mid == nums[mid]) return mid;
        int left = getMagicIdxDFS(nums, start, min(mid - 1, nums[mid]));
        if (left >= 0) return left;
        int right = getMagicIdxDFS(nums, max(mid + 1, nums[mid]), end);
        return right;
    }

http://www.shuatiblog.com/blog/2014/09/17/find-magic-index/
We cannot discard half of the input any more. Instead, we discard a range between (mid) and (array[mid]). Then check left and right part seperately.

public static int myAnswerWithDup(int[] array) {
    int len = array.length;
    return helper(array, 0, len - 1);
}

public static int helper(int[] array, int left, int right) {
    if (right < left) {
        return -1;
    }
    int mid = left + (right - left) / 2;
    if (array[mid] == mid) {
        return mid;
    } else {
        int smaller = 0;
        int larger = 0;
        if (array[mid] < mid) {
            smaller = array[mid];
            larger = mid + 1;
        } else if (array[mid] > mid) {
            smaller = mid - 1;
            larger = array[mid];
        }
        int leftResult = helper(array, left, smaller);
        if (leftResult != -1) {
            return leftResult;
        } else {
            return helper(array, larger, right);
        }
    }
}

https://codesolutiony.wordpress.com/2014/12/31/9-3-magic-index/

public int findMagicIndex(int[] num) {

    return subFind(num, 0, num.length - 1);

}

private int subFind(int[] num, int start, int end) {

    int result = -1;

    if (start > end) {

        return -1;

}

    int mid = (start + end) / 2;

    if (num[mid] == mid) {

        return mid;

}

    if (num[mid] > mid) {

        result = subFind(num, start, mid - 1) == -1 ? result = subFind(num, num[mid], end);

    } else {

        result = subFind(num, mid + 1, end) == -1 ? subFind(num, start, num[mid]);

}

    return result;

}

http://www.cnblogs.com/jdflyfly/p/3931807.html
https://gist.github.com/ivycheung1208/853f9f700439860848fe
// return one magic index if any
int magicIndex(vector<int> arr, int begin, int end) // arr[begin, end)
{
if (begin == end) { // no element left in the subarray
return -1;
}
int mid = (begin + end) / 2; // middle of the subarray
if (arr[mid] == mid)
return mid;
else if (arr[mid] < mid)
return magicIndex(arr, mid + 1, end); // examine the right subaaray
else
return magicIndex(arr, begin, mid); // examine the left subaaray
}

int magicIndex(vector<int> arr)
{
return magicIndex(arr, 0, arr.size());
}

// return all possible magic indices
void magicIndexMult(vector<int> arr, int begin, int end, vector<int> &index)
{
if (begin == end)
return;
int mid = (begin + end) / 2;
if (arr[mid] >= mid)
magicIndexMult(arr, begin, mid, index);
if (arr[mid] == mid)
index.push_back(mid);
if (arr[mid] <= mid)
magicIndexMult(arr, mid + 1, end, index);
}

vector<int> magicIndexMult(vector<int> arr)
{
vector<int> index;
magicIndexMult(arr, 0, arr.size(), index);
return index;
}

// return all possible magic indices, data not dictinct
void magicIndexMultND(vector<int> arr, int begin, int end, vector<int> &index)
{
if (begin == end)
return;
int mid = (begin + end) / 2;
if (arr[mid] >= mid) // first half
magicIndexMultND(arr, begin, mid, index);
else if (arr[mid] >= begin)
magicIndexMultND(arr, begin, arr[mid] + 1, index);
if (arr[mid] == mid) // middle
index.push_back(mid);
if (arr[mid] <= mid) // second half
magicIndexMultND(arr, mid + 1, end, index);
else if (arr[mid] < end)
magicIndexMultND(arr, arr[mid], end, index);
}

vector<int> magicIndexMultND(vector<int> arr)
{
vector<int> index;
magicIndexMultND(arr, 0, arr.size(), index);
return index;
}

int magicFast(int[] array) {
return magicFast(array, 0, array.length - 1);
}

int magicFast(int[] array, int start, int end) {
if (end< start) {
return -1;
}
int mid= (start+ end)/ 2;
if (array[mid] == mid) {
return mid;
} else if (array[mid] > mid) {
13 return magicFast(array, start, mid - 1);
} else {
return magicFast(array, mid+ 1, end);
}
}

Follow Up: What if the elements are not distinct?
The general pattern is that we compare mid Index and midValue for equality first. Then, if they are not equal, we recursively search the left and right sides as follows:
• Left side: search indices start through Math. min (midlndex - 1, midValue ).
Right side: search indices Math. max(midlndex + 1, midValue) through end.
int magicFast(int[] array) {
return magicFast(array, 0, array.length - 1);
}

int magicFast(int[] array, int start, int end) {
if (end< start) return -1;

int midindex =(start+ end)/ 2;
int midValue = array[midindex];
if (midValue == midindex) {
return midindex;
}

/* Search left */
int leftindex = Math.min(midindex - 1, midValue);
int left = magicFast(array, start, leftindex);
if (left>= 0) {
return left;
}

/* Search right */
int rightindex = Math.max(midindex + 1, midValue);
int right = magicFast(array, rightlndex, end);

return right;
}

Read full article from [CareerCup] 9.3 Magic Index 魔法序号 - Grandyang - 博客园

[CareerCup] 9.3 Magic Index 魔法序号 - Grandyang - 博客园

Labels

Popular Posts