Russell_0221

#include <iostream>
using namespace std;

int SearchMax(int a[], int n){
    int lef = 0;
    int rig = n-1;
    while(lef<=rig){
        int mid = (lef+rig)/2;
        if(a[mid]>a[mid-1] && a[mid]>a[mid+1]){
            return a[mid];
        }
        if(a[mid]>a[mid+1] ){
            rig = mid - 1;
        }
        else{
            lef = mid + 1;
        }
    }
}

int main(){
    int n;
    cin>>n;
    int a[n];
    for(int i=0; i<n; i++){
        cin>>a[i];
    }
    cout<<SearchMax(a, n);
    return 0;
}

   因為數組排序先增大在遇到最大值后減小，因此可使用二分法將數組劃分為遞增與遞減的兩部分，而最大值便存在于兩個部分的重合處。

   可設置兩個指針分別從前半部分和后半部分進行對最大值的查找，從而可以減少查找所花的時間，提高查找效率。

   當 a[mid]>a[mid-1] && a[mid]>a[mid+1] 時，說明此時a[mid]大于左側和右側的兩個數，而在該數組中符合條件的只有最大值，最大值既是a[mid]；

   當 a[mid]>a[mid+1] 時，說明此時a[mid]大于右側的數，但小于左側的數，此時a[mid]仍處于遞減數列中，則需要指針右移；

   同上，當情況相反時則需要指針左移。

4.算法時間及空間復雜度分析

   時間復雜度：因為使用了二分搜索法，所以對數組的查找時間規模減半，時間復雜度為O(log n)。

   空間復雜度：因為沒有其他的數組，所以空間復雜度為O(1)。

5.心得體會

   在這次實驗課上和搭檔進行了討論，因為對這道題的思路都一致但是打出來的代碼截然不同，所以對兩個代碼共同討論了些許時間，了解對方每一行代碼所代表的含義。

   這樣能讓我們對題目和代碼的了解更加清晰，同時能互相討論不同的思路想法。

   課后對這個題再次進行了嘗試，花了大半天時間找錯，結果是錯在return a[mid] 時，我只return mid 了……

   希望以后不要再犯這種粗心的錯。

6.分治法的個人體會和思考

  分治法便是將一個較為負責的問題化為規模較小的數個子問題，在一些情況下確實能夠提高運算效率，但在一些時候使用分治法反而會更加繁雜。

   所以在使用分治法時需要先對分治法有一定的了解，提前判斷分治法是否適應這個題目要求。