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

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.