CSI讲义10：寻找峰值（解答）

learning

题目：寻找峰值

任意给出一组数值，比如：9、12、3、7，13。如果某一个数值同时比它左边与右边的数值都大，则这个数值就是一个峰值。直观上，你可以想象一个山峰的形象。当然，如果某个数在数列的最左边，如果它比它右边的值要大，那么这个数值也是峰值。同理，如果某个数在数列的最右边，如果它比它左边的值大，它也是峰值。在上面给出的数列中，12是一个峰值，同时，13也是峰值。

问题是：如何能在一个n长的数列中找到任意一个峰值？要求是，这种方法应该尽可能快。

暴力法：

设想这样一个过程：从第一个数值a1开始，比对a1与其左右两边的数值，如果满足条件，则输出a1的值，结束过程；否则，继续比对a2 。不断迭代地做下去，直得最后一个数值an也被比对过。

int findPeak(int a[],int length)
{
//a为输入的数组
//length为数组的长度
    if(length==1)    //如果数组长度为1，则输出这个数字
      return a[0];
    for(int i=0;i<length-1;i++)  //返回第一个比左右两边数值大的数字
      if(a[i]>a[i+1])
        return a[i];
    return a[length-1];       //返回数组的最后一个值，即数组最大值
}

设数组长度为n，则这个算法最多执行n步，记为O(n)

二分法：

int findPeak(int a[],int length)
{
//a为输入的数组
//length为数组的长度
   if (length == 1)    //如果数组长度为1，则输出这个数字
    return 0;
    int left = 0, right = length - 1;
    while (right - left > 1)      //当分组中只有两个数字时，循环结束
    {
        int mid = left + (right - left) / 2;     //将分组一分为二
        if (a[mid] < a[mid + 1])
        {
            left = mid + 1;
        }
        else
        {
            right = mid;
        }
    }
//返回两个数中较大的一个值，或是返回数组中的最后一个值
    int peak=(left == length - 1 || a[left] > a[left + 1]) ? left : right;
    return a[peak];
}

设数组长度为n，则这个算法最多可以执行log n步，记为O(log n)

题目以及解题思路来自：
作者：Bintou老师
链接：http://www.jianshu.com/p/53c8dcf25b2f
來源：简书