https://leetcode.com/problems/find-peak-element/

Input: nums = [1,2,3,1]
Output: 2
Explanation: 3 is a peak element and your function should return the index number 2.

peak가 양쪽의 elem보다 크면 return 해 준다.

매 elem을 돌면서 구하면 O(n) 이 나오는건 당연하다. 따라서 더 빠르게 구해달라고 한다면 O(logn) 또는 O(1) 일 것이다. 1 은 안될테니 logn으로 간다.

이는 BST로 접근 가능하겠다.

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
	    int leftIndex = 0;
	    int rightIndex = nums.size() - 1;

	    while (leftIndex < rightIndex)
	    {
		    int pivot = (leftIndex + rightIndex) * 0.5f;
		    int num = nums[pivot];
		    int nextNum = nums[pivot + 1];
		    if (num < nextNum)
			    leftIndex = pivot + 1;
		    else
			    rightIndex = pivot;
	    }
	return leftIndex;
    }
};

Runtime: 4 ms, faster than 95.61% of C++ online submissions for Find Peak Element.

Memory Usage: 8.8 MB, less than 99.59% of C++ online submissions for Find Peak Element.

pivot 을 nums.size() * 0.5f 해놓고 왜 이러지 하고 있었다. 매번 업데이트 되어야 하는데...