Skip to content

08.03. Magic Index

Description

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. 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. 1 <= nums.length <= 1000000

Solutions

Thinking

A magic index satisfies \(nums[i]=i\). A left-to-right scan finds the smallest one in linear time.

Duplicates block the usual “compare \(mid\) to \(nums[mid]\) and drop a half” argument, because a match may still sit on the left.

Search the left half fully first (that answer is the smallest), then test the midpoint, then the right half. Worst case remains linear, but ordered data often skips ranges.

We design a function \(dfs(i, j)\) to find the magic index in the array \(nums[i, j]\). If found, return the value of the magic index, otherwise return \(-1\). So the answer is \(dfs(0, n-1)\).

The implementation of the function \(dfs(i, j)\) is as follows:

  1. If \(i > j\), return \(-1\).
  2. Otherwise, we take the middle position \(mid = (i + j) / 2\), then recursively call \(dfs(i, mid-1)\). If the return value is not \(-1\), it means that the magic index is found in the left half, return it directly. Otherwise, if \(nums[mid] = mid\), it means that the magic index is found, return it directly. Otherwise, recursively call \(dfs(mid+1, j)\) and return.

In the worst case, the time complexity is \(O(n)\), and the space complexity is \(O(n)\). Where \(n\) is the length of the array \(nums\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def findMagicIndex(self, nums: List[int]) -> int:
        def dfs(i: int, j: int) -> int:
            if i > j:
                return -1
            mid = (i + j) >> 1
            l = dfs(i, mid - 1)
            if l != -1:
                return l
            if nums[mid] == mid:
                return mid
            return dfs(mid + 1, j)

        return dfs(0, len(nums) - 1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int findMagicIndex(int[] nums) {
        return dfs(nums, 0, nums.length - 1);
    }

    private int dfs(int[] nums, int i, int j) {
        if (i > j) {
            return -1;
        }
        int mid = (i + j) >> 1;
        int l = dfs(nums, i, mid - 1);
        if (l != -1) {
            return l;
        }
        if (nums[mid] == mid) {
            return mid;
        }
        return dfs(nums, mid + 1, j);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int findMagicIndex(vector<int>& nums) {
        function<int(int, int)> dfs = [&](int i, int j) {
            if (i > j) {
                return -1;
            }
            int mid = (i + j) >> 1;
            int l = dfs(i, mid - 1);
            if (l != -1) {
                return l;
            }
            if (nums[mid] == mid) {
                return mid;
            }
            return dfs(mid + 1, j);
        };
        return dfs(0, nums.size() - 1);
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
func findMagicIndex(nums []int) int {
    var dfs func(i, j int) int
    dfs = func(i, j int) int {
        if i > j {
            return -1
        }
        mid := (i + j) >> 1
        if l := dfs(i, mid-1); l != -1 {
            return l
        }
        if nums[mid] == mid {
            return mid
        }
        return dfs(mid+1, j)
    }
    return dfs(0, len(nums)-1)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
function findMagicIndex(nums: number[]): number {
    const dfs = (i: number, j: number): number => {
        if (i > j) {
            return -1;
        }
        const mid = (i + j) >> 1;
        const l = dfs(i, mid - 1);
        if (l !== -1) {
            return l;
        }
        if (nums[mid] === mid) {
            return mid;
        }
        return dfs(mid + 1, j);
    };
    return dfs(0, nums.length - 1);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
impl Solution {
    fn dfs(nums: &Vec<i32>, i: usize, j: usize) -> i32 {
        if i >= j || nums[j - 1] < 0 {
            return -1;
        }
        let mid = (i + j) >> 1;
        if nums[mid] >= (i as i32) {
            let l = Self::dfs(nums, i, mid);
            if l != -1 {
                return l;
            }
        }
        if nums[mid] == (mid as i32) {
            return mid as i32;
        }
        Self::dfs(nums, mid + 1, j)
    }

    pub fn find_magic_index(nums: Vec<i32>) -> i32 {
        Self::dfs(&nums, 0, nums.len())
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * @param {number[]} nums
 * @return {number}
 */
var findMagicIndex = function (nums) {
    const dfs = (i, j) => {
        if (i > j) {
            return -1;
        }
        const mid = (i + j) >> 1;
        const l = dfs(i, mid - 1);
        if (l !== -1) {
            return l;
        }
        if (nums[mid] === mid) {
            return mid;
        }
        return dfs(mid + 1, j);
    };
    return dfs(0, nums.length - 1);
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    func findMagicIndex(_ nums: [Int]) -> Int {
        return find(nums, 0, nums.count - 1)
    }

    private func find(_ nums: [Int], _ i: Int, _ j: Int) -> Int {
        if i > j {
            return -1
        }
        let mid = (i + j) >> 1
        let l = find(nums, i, mid - 1)
        if l != -1 {
            return l
        }
        if nums[mid] == mid {
            return mid
        }
        return find(nums, mid + 1, j)
    }
}

Comments