[LeetCode] Find Peak Element

A peak element is an element that is greater than its neighbors.

Given an input array where num[i] ≠ num[i+1], find a peak element and return its index.

The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.

You may imagine that num[-1] = num[n] = -∞.

For example, in array [1, 2, 3, 1], 3 is a peak element and your function should return the index .
umber 2.

• 实现代码1

/*************************************************************
    *  @Author   : 楚兴
    *  @Date     : 2015/2/7 12:59
    *  @Status   : Accepted
    *  @Runtime  : 8 ms
*************************************************************/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
    int findPeakElement(const vector<int> &num) {
        int len = num.size();
        for (int i = 1; i < len; i++)
        {
            //因为num[i-1]必大于num[i-2],所以此处省去一个判断
            if (num[i] < num[i - 1])
            {
                return i - 1;
            }
        }
        return len - 1;
    }
};

• 实现代码2

/*************************************************************
    *  @Author   : 楚兴
    *  @Date     : 2015/2/7 13:49
    *  @Status   : Accepted
    *  @Runtime  : 8 ms
*************************************************************/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
    int findPeakElement(const vector<int> &num) {
        return find(num, 0, num.size() - 1);
    }

    int find(const vector<int> &num, int left, int right)
    {
        if (left == right)
        {
            return left;
        }
        int mid1 = (left + right) / 2;
        int mid2 = mid1 + 1;
        if (num[mid1] > num[mid2])
        {
            return find(num,left,mid1); 
            //左边满足初始数组的条件,即第一个数大于第0个数，第size个数大于第size+1个数
        }
        else
        {
            return find(num,mid2,right);
        }
    }
};