1．单峰序列

问题描述

给定含有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

输出：0

思路：每次折半查找，看峰值是否出现在两边，最后合起来看峰值是否出现在整个区域。

#include<iostream>

using namespace std;

int n;
int *a;
int Pos;
int flag;
int judge;

void solve(int l, int r){ 
    if (judge == -1) return;
    int mid = (l + r) / 2;
    if (r - l < 2 ) return;
    if (a[mid - 1] == a[mid] || a[mid - 1] == a[mid + 1] || a[mid] == a[mid] + 1 || flag == -1)
        return;
    solve(l, mid);
    solve(mid, r);
    if (a[mid] <= a[mid -1] && a[mid] <= a[mid + 1]){
        judge = -1;
        return;
    }    
    if (a[mid] > a[mid - 1] && a[mid] > a[mid + 1]){
        Pos = mid;
        if (flag == 1) {
            flag = -1;
            Pos = -1;
        }
        else flag = 1;    
    }        
}

int main(){
    Pos = flag  = judge = 0;
    scanf("%d", &n);
    a = new int[n];
    for(int i = 0; i < n; i++)
        scanf("%d", &a[i]);
    int f = 0;
    for (int i = 1; i <= 2 * n; i *= 2)
        if(i == n) f = 1;
    //处理数量是2的幂次情况
        if (f == 1) {
        int flag1 = 0, Pos1 = 0; 
        solve(1, n - 1);
        flag1 = flag;
        Pos1 = Pos;
        flag  = Pos = 0;
        solve(0, n - 2);
        if (flag < 0 || flag1 < 0 || flag == 0 && flag1 == 0|| flag == 1 && flag1 == flag && Pos1 != Pos) {
            printf("0
");
            return 0;
        }
        if (flag1 == 1 && flag == 0) {
            flag = 1;
            Pos = Pos1;
        }    
    }
    else solve(0, n - 1);
    if (judge < 0) {
        printf("0
");
        return 0;    
    }
    if (flag == 0) printf("0
"); 
    else printf("%d", Pos + 1);
    return 0;
}