力扣每日一題——面試題 08.03. 魔法索引

題目描述

魔術索引。 在數組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;
    }