题目描述
魔术索引。 在数组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,即数组中可能包含重复元素的版本
来源:力扣(LeetCode)
链接:魔法索引
著作权归领扣网络所有。
解题方法
1.暴力枚举
这个方法最通俗易懂,将数组从左遍历到右,遍历当中第一个满足魔法索引的元素就是本题的答案。
2.二分减枝
每次都选取中间的元素,如果这个元素是魔法索引的话,则有两种可能,第一种可能是这个元素就只最优的魔法索引,第二种可能是最优的魔法索引在该索引的左边,不可能在该索引的右边。如果这个元素不是魔法索引,则可以确定,该索引的左边和右边都有可能存在最优魔法索引,并且一旦确定了左边有魔法索引就不用再去搜索右边了,所以我们选择先搜索左边,若找到最优魔法索引则直接返回,若没找到再去搜索右边。
代码如下:
void a(vector<int>&n,int start,int end,int &ans){
if(start>end){ //递归退出条件
return;
}
int mid=(start+end)/2; //获得数组中心的索引
//若中间的符合魔法索引的条件,则记录索引并搜索该索引的左侧
if(mid ==n[mid]){
ans=mid;
return a(n,start,mid-1,ans);
}
else{
a(n,start,mid-1,ans); //优先搜索左边
//若搜索完左侧后无结果或者结果不是最优解,则搜索右侧
if(ans==-1||ans>end){
return a(n,mid+1,end,ans);
}
}
}
int findMagicIndex(vector<int>& n) {
int ans=-1;
a(n,0,n.size()-1,ans);
return ans;
}