面试题 08.03. 魔术索引
题目来源：力扣（LeetCode）https://leetcode-cn.com/problems/magic-index-lcci
题目
魔术索引。 在数组A[0...n-1]中，有所谓的魔术索引，满足条件A[i] = i。给定一个有序整数数组，编写一种方法找出魔术索引，若有的话，在数组A中找出一个魔术索引，如果没有，则返回-1。若有多个魔术索引，返回索引值最小的一个。
示例1:
输入：nums = [0, 2, 3, 4, 5]
输出：0
说明: 0下标的元素为0
示例2:
输入：nums = [1, 1, 1]
输出：1
说明:
- nums长度在[1, 1000000]之间
- 此题为原书中的 Follow-up，即数组中可能包含重复元素的版本
解题思路
思路：剪枝，分治
这里先提一下，只是看本题的话，可能会有些争议，后面再解释。
现在先审题，理清其中的关键点：
- 给定的数组是有序的（题目中只说有序，并未说是升序还是降序，这里结合示例，先默认是升序）；
- 题目要求的魔术索引，即是满足条件 A[i] = i；
- 数组中可能存在多个魔术索引，存在时，返回索引值最小的；
- 不存在魔术索引，则返回 -1。
现在，结合上面罗列的关键点，可以发现数组有序（前面说了先默认升序），即使存在多个魔术索引，返回的也是最小索引的一个。那么现在能直接想到的就是直接遍历数组，当满足条件 nums[i]==i，直接返回即可，没有就返回 -1。相关代码大致如下：
class Solution:
def findMagicIndex(self, nums: List[int]) -> int:
for i in range(len(nums)):
if nums[i] == i:
return nums[i]
return -1
就前面开篇说的争议，稍微吐槽下，当写完上面段代码时，总觉得事情没那么简单。后面去翻阅了官方题解下的评论，的确有很大的争议。
这里大致说下，只看本题的话，最直观的就是直接遍历，暴力法解决。可以回顾下题目，题目最后的说明中提及到 【此题为原书中的 Follow-up，即数组中可能包含重复元素的版本】。
这里说的是此题是可能存在重复元素的版本，所以笔者也去翻阅了原题。查阅的结果是，原题是有两部分：
- 一个是给定数组升序，元素值各不相同，要求给定的数组中是否存在魔术索引；
- 另一个是给定不下降序列，元素值可能相同，求是否存在魔术索引。（也就是本题）
而且题目中 说明：思考是否存在一个复杂度优于 O(n) 的方法。
那么就现在就查阅的资料结合本题，进行展开说明。
这里，在原题第一部分的基础上，重新来看这题。题目中说明，【有可能存在多个魔术索引，元素可能重复】。那我们将情况分开讨论：
- 首先先讨论，当只有一个魔术索引时。
我们先假设存在魔术索引 i，那么也就意味着 [0, i-1] 这个区间中，索引对应的值均小于索引值，而 [i+1, n-1] 这个区间的索引对应的值则均大于索引值。我们举个例子来说明，例如给定如下数组：
nums = [-1, 0, 1, 3, 5]
那么，上面数组中每个索引对应的元素值与索引的差值如下：
[-1, -1, -1, 0, 1]
可以看到，上面的数组是具有单调性的，那么我们只要使用二分查找，找到 0 所在的位置，返回答案即可。
- 再看可能存在多个魔术索引的情况，这里也同样将可能重复的情况引入进来。
假设存在这样的一个数组
nums = [0, 0, 1, 1, 4, 6]
还是按照前面的策略，用元素值减去元素对应的索引，得：
[0, -1, -1, -2, 0, 1]
现在，我们可以看到，结果并不具备单调性，在这里不能够直接用二分查找的方法去解决。在这里，我们要进行适当的剪枝，具体的做法如下：
- 同样还是先取中间元素，如果中间元素刚好是魔术索引，这个时候要注意，因为有可能有多个魔术索引，当前的魔术索引并不是最小的那个。但是我们可以确定的是，中间元素右侧的索引值较大，即使存在魔术索引也不是更小的那个，那么此时可以抛开右侧部分，转而去查找左侧部分是否还有更小的魔术索引。
- 如果中间元素不是魔术索引，这里无法确定魔术索引可能存在于哪侧。这个时候，两边都要进行搜索。
在这里，根据上述的做法，我们用递归的方法去搜索。
具体代码实现如下（含注释）。
再啰嗦一句，其实到最后，使用递归的方法，也是往左侧找答案，反而有可能影响效率。不过，这也是一种方法，当然也可以不追究原题如何，直接一次遍历查找答案。
代码实现
class Solution:
def findMagicIndex(self, nums: List[int]) -> int:
return self.find_magic_index(nums, 0, len(nums) - 1)
def find_magic_index(self, nums, left, right):
# 未找到的符合要求的返回 -1
if left > right:
return -1
# 取中间元素
mid = left + (right - left) // 2
# 先看是否能找到第一个魔术索引，先往左侧找
left_ans = self.find_magic_index(nums, left, mid-1)
# 如果左侧存在，那么返回 left_ans
if left_ans != -1:
return left_ans
# 如果不存在，先比较 nums[mid] == mid
elif nums[mid] == mid:
return mid
# 不存在，且 nums[mid] != mid 时，往右侧寻找
return self.find_magic_index(nums, mid + 1, right)
实现结果
欢迎关注
公众号 【书所集录】
