Problem Description

Problem ID: 162

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

Given an integer array nums, find a peak element, and return its index. If the array contains multiple peaks, return the index to any of the peaks.

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

You must write an algorithm that runs in O(log n) time.

Difficulty

Medium

Solution

Explanation

Edge case: Empty array

Binary search. When the left and right pointer meet at the same element, that element is the peak.

Time: O(log N) Space: O(1)

Implementation

int findPeakElement(vector<int>& nums) {
	int low = 0, high = nums.size() - 1;
	while (low < high) {
		int mid = low + (high - low) / 2;
		if (nums[mid] < nums[mid + 1]) {
			low = mid + 1;
		} else {
			high = mid;
		}
	}
	return low;
}