Find Peak Element

주어진 배열에서 Peak를 찾아라.

peak란 배열의 요소 중에서 양 옆의 값보다 큰 요소의 인덱스를 뜻한다.

[1, 2, 3, 5, 4]  -> Peak : 5
[1, 3, 2, 4, 5, 7, 6] -> Peak : 7

가장 쉬운 방법으로는 배열을 순회 하면서 양 옆의 값보다 큰 요소를 찾는 방법이 있겠다. (O(n))

그러나 가장 효율적인 방법은 O(logN)의 방법. 즉 Binary Search를 이용하는 것이다.

즉 나열된 값들의 중간 값(Pivot)을 찾고 그 다음 값이 Pivot 값보다 크면 오른쪽, 작으면 왼쪽으로 인덱스를 옮기는 방식으로 탐색을 진행 한다. 

#include <iostream>

int findPeakElement(int* nums, int numSize)
{
    int left = 0;
    int right = numSize - 1;

    // 배열의 크기
    if(numSize <= 1)   return 0;

    while (left < right)
    {
        int pivot = (left + right) / 2;
        int num = nums[pivot];
        int nexNum = nums[pivot + 1];

        if (num < nexNum)
        {
            // 이 경우 Peak는 num의 오른쪽에 있다.
            left = pivot + 1;
        }
        else
        {
            right = pivot;
        }
    }
    //return left;
    return right;
}


int main()
{
    int numSize = 7;
    int nums[] = { 1, 3, 2, 4, 5, 7, 6};

    int peak = findPeakElement(nums, numSize);

    std::cout << "peak : " << peak << std::endl;
}