Find a Peak Element

medium binary search

Problem

Given an array where adjacent elements differ, return any index whose value is greater than both neighbours (treat indices outside the array as −∞). Use binary search: at each step, compare the midpoint to its right neighbour and walk uphill.

Inputnums = [1, 4, 3, 5, 2]

Output1 or 3

Index 1 (value 4) and index 3 (value 5) are both peaks; either is acceptable.

nums (comma-separated, no two adjacent equal)

def find_peak(nums):
    l, r = 0, len(nums) - 1
    while l < r:
        m = (l + r) // 2
        if nums[m] < nums[m + 1]:
            l = m + 1
        else:
            r = m
    return l

function findPeak(nums) {
  let l = 0, r = nums.length - 1;
  while (l < r) {
    const m = (l + r) >> 1;
    if (nums[m] < nums[m + 1]) l = m + 1;
    else r = m;
  }
  return l;
}

class Solution {
    public int findPeak(int[] nums) {
        int l = 0, r = nums.length - 1;
        while (l < r) {
            int m = (l + r) >>> 1;
            if (nums[m] < nums[m + 1]) l = m + 1;
            else r = m;
        }
        return l;
    }
}

int findPeak(vector<int>& nums) {
    int l = 0, r = (int)nums.size() - 1;
    while (l < r) {
        int m = (l + r) / 2;
        if (nums[m] < nums[m + 1]) l = m + 1;
        else r = m;
    }
    return l;
}

Time: O(log n) Space: O(1)