Binary Search Solution for LeetCode 162: Find Peak Element

The problem requires locating a peak element in an integer array where elements outside the array are considered negative infinity (‑∞). A peak is defined as an element greater than both its left and right neighbors, and the algorithm must run in O(log n) time.

Because the required complexity is logarithmic, a binary‑search strategy is appropriate. The method maintains two pointers, left and right, initially set to the first and last indices of the array. At each iteration, the midpoint mid is computed as left + (right - left) / 2. The element at mid is then compared with its adjacent elements to determine which side contains a peak.

Three scenarios are considered:

If nums[mid-1] < nums[mid] > nums[mid+1], mid itself is a peak and the index is returned.

If nums[mid] < nums[mid+1], the right neighbor is larger, so the search moves to the right half by setting left = mid + 1.

If nums[mid] < nums[mid-1], the left neighbor is larger, so the search moves to the left half by setting right = mid - 1.

The following pseudocode illustrates the binary‑search loop:

left, right := 0, len(nums)-1
while left <= right {
    mid := left + (right-left)/2
    if nums[mid-1] < nums[mid] && nums[mid] > nums[mid+1] {
        return mid
    } else if nums[mid] < nums[mid+1] {
        left = mid + 1
    } else {
        right = mid - 1
    }
}

A complete Go implementation is provided below. It defines a helper get(i int) int that returns math.MinInt for out‑of‑range indices, satisfying the problem’s “‑∞” requirement.

func findPeakElement(nums []int) int {
    n := len(nums)

    get := func(i int) int {
        if i < 0 || i >= n {
            return math.MinInt // out‑of‑range treated as -∞
        }
        return nums[i]
    }

    left, right := 0, n-1
    for left <= right {
        mid := left + (right-left)/2 // middle index
        // peak condition
        if get(mid) > get(mid+1) && get(mid) > get(mid-1) {
            return mid
        } else if get(mid) < get(mid+1) { // ascend to the right
            left = mid + 1
        } else if get(mid) < get(mid-1) { // ascend to the left
            right = mid - 1
        }
    }
    return 0 // fallback, should never reach here for valid input
}

The algorithm guarantees logarithmic time because each iteration halves the search interval, and it correctly handles edge cases by treating indices outside the array as negative infinity.