面试题 08.03

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 integers, write a method to find a magic index, if one exists, in array A. If not, return -1. If there are more than one magic index, return the smallest one.

Example1:

Input: nums = [0, 2, 3, 4, 5] Output: 0 Example2:

Input: nums = [1, 1, 1] Output: 1 Note:

1 <= nums.length <= 1000000 This problem is the follow-up of the original problem in the book, i.e. the values are not distinct.

Solutions

• If the array does not contain duplicate elements, the problem can be solved by binary search O(nlog(n)).

  • If there are duplicates, it's not possible to decide the searching direction.

if we meet nums[mid] < mid, the magic number may be in both sides

x x 3 4 x x x index  if there are no duplicates, all indexes <= 4 are not possible
    3 3       nums

x x x 4 5 x x index 
      3 5     nums

class Solution {
public:
    int findMagicIndex(vector<int>& nums) {
        int lo = 0, hi = nums.size();

        while (lo < hi) {
            int mid = lo + ((hi - lo) >> 1);
            if (nums[mid] < mid)
                lo = mid + 1;
            else
                hi = mid;
        }

        return lo < nums.size() && nums[lo] == lo ? lo : -1;
    }
};

1. jump forward O(n)

class Solution {
public:
    int findMagicIndex(vector<int>& nums) {
        int i = 0;
        while (i < nums.size()) {
            if (nums[i] == i)
                return i;
            else
                i = max(nums[i], i + 1);
        }

        return -1;
    }
};

1. divide and conquer O(n)

2. Check the official answer.