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 int findPeakElement(int* nums, int numSize) { int left = 0; int ri..
2021. 10. 25.
