Algorithm

LintCode/Find Peak Element

Problem Summary

A is an array with N integers which has the following features:

  1. The numbers in adjacent positions are different.
  2. A[0] < A[1] && A[N - 2] > A[N - 1].

We define a position P is a peak if: A[P] > A[P-1] && A[P] > A[P+1]

Find a peak element in this array.

Solution

The O(N) solution is trivial. But can we solve this with a time complexity of O(logN)?

We can think of binary search immediately. The key is whether we can rule out half the indices each time. When we find A[mid]A[mid+1], we can toss out [mid+1,right].

In this way, we can reduce the time complexity to O(logN).

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    /*
     * @param A: An integers array.
     * @return: return any of peek positions.
     */
    int findPeak(vector<int> &A) {
        int l = 0, r = A.size()-1, mid;
        while (l<r)
        {
            mid = (l+r)>>1;
            if (A[mid]>A[mid+1])
                r = mid;
            else
                l = mid+1;
        }
        return l;
    }
};