7-1 maximum number in a unimodal array

1.实践题目名称

　　7-1 maximum number in a unimodal array

2.问题描述

　　在一个单峰的数组中找到最大值作为输出，要求时间复杂度为O（log n）。

3.算法描述

• 　　二分搜索算法
• 　　递归算法

　　由于数组先递增后递减，必定存在最大值，我们采用二分搜索算法，定义mid指向数组中间元素。

　　当a[mid-1]>=a[mid]&&a[mid+1]<=a[mid]代表mid在数组递减区间，最大值位于mid左边，因此递归数组左部，right=mid-1

　　当a[mid-1]<=a[mid]&&a[mid+1]<=a[mid]代表mid在数组递增区间，最大值位于mid左边，因此递归数组右部，left=mid+1

　　当a[mid-1]=a[mid]&&a[mid+1]<=a[mid]代表mid在数组最大值处，返回mid

4.算法时间及空间复杂度分析

时间复杂度分析：

　　采用二分搜索，每次循环都取当前数组的中间位置，时间复杂度为O（log n）。

空间复杂度分析：

　　只用到一个数组接取输入信息，空间复杂度为O（1）。

5.心得体会

　　本次的实践课中我们一共解出两题。主要使用了分治法。此次分工是我们三个人先各做各的题，若谁先做出则给对方讲解思路。如在求解根的那题，看不出自己的代码的错误，一直运行结果错误，花费了不少时间，所幸我的同伴在不久后做出了答案，给我讲解了她的思路。但中途仍遇到了很多困难，如大家都对第三题如何在时间复杂度O（log n）完成感到疑惑，没有思路，只能想到很多时间复杂度更高的解法。

6.分治法的个人体会和思考

　　分治法为将大问题化为小问题，分为分、治、并：