【算法】单峰序列

单峰序列

      问题描述

给定含有n个不同整数的数组L=<a1,a2,......,an>,如果L中存在ai,使得a1<a2<......<ai-1<ai>ai+1>…>an。则称L是单峰的，并称ai是L的“峰顶”。假设L是单峰的，设计一个算法，找L的峰顶。

输入形式

一共包括两行，第一行一个整数N，表示数组中整数的个数。

接下来的一行中包含N个整数，以空格分隔

输出形式

如果这些整数中存在峰顶元素ai,则输出该元素的下标i，否则输出0

样例输入

  9

1 2 5 7 9 8 6 4 3

样例输出

  5

另一组样例：

输入：

9

3 5 6 2 9 8 7 4 1

输出：

解题思路：

用二分法将序列一分为二，假设一个小的分段只有三个数值，比较这三个数的大小，来决定左右界的调整。同时要注意符合要求的这个分组左右边的其他分组是否符合要求，若不符合则当前分组也不符合要求。

#include<iostream> 
using namespace std;
int Summit(int l[],int left,int right){
	if(left+1==right) return -1;
	int middle = (left + right+1)/2;
	if( ( l[middle-1]<l[middle] ) && ( l[middle]<l[middle+1] ) )
		return Summit(l,middle,right);
	else if( ( l[middle-1]>l[middle] ) && ( l[middle]>l[middle+1] ) )
		return Summit(l,left,middle);
	else if( ( l[middle-1]<l[middle] ) && ( l[middle]>l[middle+1] ) )
		if(Summit(l,left,middle)<0 && Summit(l,middle,right)<0 )
			return middle;
		else return -1;
	else return -1;
}
int main(){
	int N,L[20];
	cin>>N;
	for(int i=0;i<N;i++)
		cin>>L[i];
	cout<<Summit(L,0,N-1)+1;
	return 0;
}