Find Peak Element

Description

There is an integer array which has the following features:

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

We define a position P is a peek if:
A[P] > A[P-1] && A[P] > A[P+1]
Find a peak element in this array. Return the index of the peak.

Example
Given [1, 2, 1, 3, 4, 5, 7, 6]
Return index 1 (which is number 2) or 6 (which is number 7)

Challenge
Time complexity O(logN)

Link

Lintcode_ladder

Method

1. Binary search
2. x

Example

1. 1

class Solution {
public:
    /**
     * @param A: An integers array.
     * @return: return any of peek positions.
     */
    int findPeak(vector<int> nums) {
        // write your code here
         if (nums.empty()) {
            return -1;
        }
        int start = 0;
        int end = nums.size()-1;
        while (start+1 < end) {
            int mid = start+(end-start)/2;
            // int left = mid-1;
            // int right = mid+1;
            // if,      left must have peak
            // else if, right must have peak
            // else   , in the valley, left or right is ok
            if (nums[mid] < nums[mid-1]) {
                end = mid;
            } else if (nums[mid] < nums[mid+1]) {
                start = mid;
            } else {
                end = mid;
            }
        }
        if (nums[start] < nums[end]) {
            return end;
        } else {
            return start;
        }
        return -1;
    }
};

Similar problems

x

Tags

x