难度: Easy
魔术索引。 在数组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
说明:
运行时间: 18 ms
内存: 16.9 MB
class Solution:
def findMagicIndex(self, nums: List[int]) -> int:
#最快的是2分
#但是2分怎么找到最左边的那个？
for a in range(0,len(nums)):
if nums[a]==a:
return a
return -1
此题解采用了直接的线性搜索方法。从数组的第一个元素开始遍历，一旦发现某个索引i满足条件nums[i] == i，即判断为魔术索引，立即返回该索引。如果遍历完整个数组都没有找到符合条件的索引，则返回-1。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def findMagicIndex(self, nums: List[int]) -> int:
# 遍历数组的每个元素
for index in range(0, len(nums)):
# 如果当前元素值等于其索引，则找到魔术索引
if nums[index] == index:
return index
# 如果没有找到任何魔术索引，返回-1
return -1
在一般情况下，对于有序数组，二分搜索确实是一个更高效的选择。然而，对于魔术索引的查找问题，仅当数组元素严格递增且没有重复时，二分搜索才是有效的。这是因为二分搜索依赖于能够根据中间值的比较排除一半的搜索区域。如果数组中包含重复元素，这个条件可能会被破坏，因为即使中间元素不满足条件，满足条件的元素可能位于任何一侧。因此，在不确定数组特性的情况下，使用线性搜索是一种保证找到魔术索引的可靠方法，尽管其时间复杂度较高。
线性搜索方法从数组的起始位置向后遍历，一旦找到满足条件的索引即返回，因此它能保证找到的是最小的魔术索引。即使数组中有重复元素，此方法仍然有效，因为它总是返回第一个找到的满足 nums[i] == i 的索引。
即使当前元素的值大于其索引，线性搜索还是需要继续向后查找。这是因为后续的索引值增加，可能存在某个更大的索引i，使得 nums[i] == i。只有当确定后面不可能存在满足条件的索引时（例如在某种特定的数组结构中），才可以提前终止搜索。但在一般情况下，不能因为当前元素值大于索引就停止搜索。