1.实践题目名称

   7-1 maximum number in a unimodal array 

2.问题描述

#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.分治法的个人体会和思考

  分治法便是将一个较为负责的问题化为规模较小的数个子问题，在一些情况下确实能够提高运算效率，但在一些时候使用分治法反而会更加繁杂。

   所以在使用分治法时需要先对分治法有一定的了解，提前判断分治法是否适应这个题目要求。