# LeetCode: Find Peak Element ## Native solution with Linear Scan

The naive solution is scan the array, check whether a element is peak.

Time complexity: $$O(N)$$.

class Solution {
public:
int findPeakElement(vector<int>& nums) {
if(nums.size() == 1) return 0;
for(int i=0 ;i<nums.size(); i++) {
int left = i - 1 >= 0 ? nums[i-1] : INT_MIN;
int right = i + 1 < nums.size() ? nums[i+1] : INT_MIN;
if(nums[i] > left && nums[i] > right)
return i;
}
return -1;
}
};


Because we can return any peak, so there are 3 cases:

1. arr is peak 1. arr[arr.size()-1] is peak 1. peak is in the range of 1...arr.size()-2 In this case, we just need to find the first index, which meets the condition of arr[index] > arr[index + 1]. So we can make the code more simpler:

class Solution {
public:
int findPeakElement(vector<int>& nums) {
for(int i=0; i<nums.size() - 1; i++) {
if(nums[i] > nums[i+1])
return i;
}
return nums.size() - 1;
}
};


## Approach with binary search

Using recursive binary search, the time complexity is $$O(logN)$$.

class Solution {
public:
int binary_search(vector<int>& nums, int left, int right) {
if(left == right) return left;
int mid = (left + right) / 2;
if(nums[mid] > nums[mid+1])
return binary_search(nums, left, mid);
else
return binary_search(nums, mid+1, right);
}

int findPeakElement(vector<int>& nums) {
return binary_search(nums, 0, nums.size()-1);
}
};

Don't miss out!