LeetCode Find Peak Element: Invariant and Why Binary Search Works

Overview

The key invariant for why binary search could solve LeetCode find peak element problem is explained in detail and a three line linear search code is given too.

LeetCode 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.

Note:Your solution should be in logarithmic complexity.

Well, although the linear approach is intuitive, but one very important fact could be utilized to write extremely elegant code with only 3 lines and handling all the special cases well (empty input, single number input, etc.) and this fact could help understand why the binary search could be adopted to solve the problem too which I will explain in detail after giving out the key fact.

Key Fact/Invariant: In linear search, starting from i = 1, suppose the current is the i – 1, then if A[i - 1] > A[i], we conclude that A[i-1] is the local peak, if not, then it must be A[i -1] < A[i], and A[i] would be in the same role as A[i-1], that is, A[i] has its left side smaller than A[i], we keep this invairant: A[i-1] > A[i-2] if we stays in the for loop.

The above key fact gives the following extremely elegant code (only 3 lines) to be accepted by LeetCode OJ to pass this Find Peak Element problem:

int findPeakElement(const vector &num) {
    for (int i = 1;  i < num.size(); ++i)
        if (num[i - 1] > num[i]) return i - 1;
    return num.size() - 1;
}

And we could also see that even the special cases like zero number input (size = 0) and one number input (size = 1) are handled quite well.

Why Binary Search Works

Well, now let’s see why we can adopt the binary search approach here, that is, if the middle one is not the peek, then we can decide the local peak is either in the left part or the right part. Then why? A lot of people including me seems do not accept the binary search method until they see the reasons. OK, now let’s start to explore why and I will try to prove it is correct and guaranteed to find the local peak if there are any.

1) Goal: Find the peak number in the interval [L, R], that is, among the numbers A[L], A[L + 1], … A[R], both end included

2) Binary Search: Always test the middle number A[M] where M = (L + R) / 2 in [L, R] against its neighbors, if it is the peak, then return, if A[M] < A[M + 1], then search the right part by setting L = M + 1, otherwise, search the left part by setting R = M – 1.

3) Proof: when why the above binary search can work correctly? This could be proved step by step as follows:

  1. A[L] > A[L-1] and A[R] > A[R+1] these two are always true (invariant). Initially, A[-1] and A[n] are assumed to be INT_MIN, so it is correct, as the binary search proceeds, it is always only one end is reset, in either cases, the left end or the right end is reset to the larger neighbor of the middle number which keeps these two statements (invariant) always true.
  2. As the algorithm indicates,  if A[M] < A[M + 1], we set L = M + 1, and we  search [M+1, R], we only need to prove there must be a peak number within [M+1, R], and the other case is similar and then we are done.
  3. Assume all of the numbers A[k] where k belongs to [L = M+1, R] are not a peak number by our definition, we must have for any k within [L, R] (note L is reset to M+1), it is either A[k] < A[k-1] or A[k] < A[k+1] for any k in [L, R]()**, please keep this key assumption** () in mind. Let’s take a look at A[L] then, in step 1, we proved that A[L] > A[L-1] combined with the assumption A[k] < A[k-1] or A[k] < A[k+1] for any k in [L, R](*), we concluded that A[L] < A[L + 1], actually, for any number A[k], we already prove that A[k] < A[k+1] where k is within [L, R], now let’s take a look at A[R], we now know A[R] > A[R-1] by our assumption, and from the invariant in step 1, we know A[R] > A[R+1], so A[R] is exactly the peak number, this is contrast to out assumption. We concluded that our assumption cannot be true. So the fact is that there must be peak numbers in [L, R]. We finish our proof here.

4) Code: The following binary search code is accepted by LeetCode OJ to pass this Find Peak Element problem:

int findPeakElement(const vector<int> &num) {
    int n = num.size();
    if (n <= 1) return n - 1;

    int left = 0, right = n - 1;
    int mid = -1;
    while (left <= right) {
        mid = left + (right - left) / 2;
        int nl = INT_MIN;
        if (mid > 0)
            nl = num[mid - 1];
        int nr = INT_MIN;
        if (mid + 1 < n)
            nr = num[mid + 1];

        if (num[mid] > nl && num[mid] > nr)
            return mid;

        if (num[mid] < nl) {
            right = mid - 1;
            continue;
        }

        if (num[mid] < nr)
            left  = mid + 1;
    }
    return -1;
}

Summary

The key invariant for why binary search could solve LeetCode find peak element problem is explained in detail and a three line linear search code is given too.

Written on December 19, 2014