Find Peak Element

Find any element bigger than both neighbours in O(log n) by binary searching toward the higher neighbour.

The idea

Values just outside the array count as −∞, and no two neighbours are equal, so walking uphill from anywhere must stop at a peak. Look at mid and mid + 1. If the line rises, a peak lies to the right of mid; if it falls, mid itself or something to its left is a peak. Keep the half that must contain one; the window shrinks until it is a single index.

Code

public static int FindPeakElement(int[] nums) {
    int lo = 0, hi = nums.Length - 1;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] < nums[mid + 1]) lo = mid + 1;
        else hi = mid;
    }
    return lo;
}

Tips

• Compare with mid + 1, which always exists while lo < hi because mid < hi.
• hi = mid, not mid - 1, when the slope falls: mid may be the peak itself.
• The array does not need to be sorted. Binary search works on any rule that tells you which half still holds an answer.

In the .NET library

lo + (hi - lo) / 2 rounds down, which keeps mid + 1 inside the array, and avoids the overflow that (lo + hi) / 2 can hit.