144. Find Peak Element

If nums[mid] < nums[mid+1], the right side is "climbing" — there must be a peak to the right (or at mid+1). Else there's a peak at mid or to the left. That halving rule finds some peak in O(log n).

Approach

l = 0, r = n - 1
while l < r:
    mid = (l + r) // 2
    if nums[mid] < nums[mid + 1]: l = mid + 1
    else:                          r = mid
return l

Because nums[-1] = nums[n] = -∞ (implicit), the algorithm always converges.

class Solution {
    public int findPeakElement(int[] nums) {
        int l = 0, r = nums.length - 1;
        while (l < r) {
            int mid = (l + r) / 2;
            if (nums[mid] < nums[mid + 1]) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        return l;
    }
}