Example: Find Peak - rFronteddu/general_wiki GitHub Wiki

A peak element is an element that is strictly greater than its neighbors.

Given a 0-indexed integer array nums, find a peak element, and return its index. If the array contains multiple peaks, return the index to any of the peaks.

You may imagine that nums[-1] = nums[n] = -∞. In other words, an element is always considered to be strictly greater than a neighbor that is outside the array.

You must write an algorithm that runs in O(log n) time.

class Solution {
    public int findPeakElement(int[] nums) {
        // the input array is not sorted so this doesn't make much sense...
        int left = 0;
        int right = nums.length - 1;

        while (left < right) {
            int mid = left + (right - left) / 2;

            if (nums[mid] < nums[mid + 1]) {
                // Move towards the right side
                left = mid + 1;
            } else {
                // Move towards the left side (or stay at the current mid)
                right = mid;
            }
        }

        // At this point, left == right, and it is a peak element
        return left;
    }
}