# int32bit / leetcode

Fetching latest commit…
Cannot retrieve the latest commit at this time.
Type Name Latest commit message Commit time
..
Failed to load latest commit information.
in.txt
solve.cpp

## Find Peak Element

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

Given an input array where num[i] ≠ num[i+1], find a peak element and return its index.

The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.

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

For example, in array `[1, 2, 3, 1]`, `3` is a peak element and your function should return the index number `2`.

click to show spoilers. Note:

Your solution should be in logarithmic complexity.

Credits: Special thanks to @ts for adding this problem and creating all test cases.

## Solution 1

```int findPeakElement(vector<int> &a) {
int n = a.size();
if (n < 2 || a[0] > a[1])
return 0;
if (a[n - 1] > a[n - 2])
return n - 1;
for (int i = 1; i < n - 1; ++i)
if (a[i] > a[i - 1] && a[i] > a[i + 1])
return i;
}```

## Solution 2

```int findPeakElement(vector<int> &a) {
int n = a.size();
for (int i = 0; i < n - 1; ++i)
if (a[i] > a[i + 1])
return i;
return n - 1;
}```

## Solution 3

• `a[mid] > a[mid + 1] && a[mid] > a[mid - 1]`, 返回mid, 否则下一步
• `a[mid] > a[mid + 1], right = mid`, 否则下一步
• `a[mid] < a[mid - 1], left = mid + 1`
• 重复直到`left == right`, 此时left就是Peak元素索引
```int fastFindPeakElement(vector<int> &a) {
int n = a.size();
int left = 0, right = n - 1;
while (left < right) {
int mid = (left + right) >> 1;
printf("left = %d, mid = %d, right = %d\n", left, mid, right);
if (a[mid] > a[mid - 1] && a[mid] > a[mid + 1])
return mid;
if (a[mid] > a[mid + 1])
right = mid;
else
left = mid + 1;
}
return left;
}```
You can’t perform that action at this time.