Binary Search for Peak Element

Finding a peak element in an array, where a peak is an element greater than its immediate neighbors, can be efficiently solved even in unsorted data by adapting the binary search algorithm. This technique doesn't require a fully sorted array but instead uses local slope information to guide the search.

The Slope Property Intuition

Unlike traditional binary search, which relies on global sorted order, finding a peak element uses a "slope property." A peak element is defined as an element greater than both its left and right neighbors (if they exist). For boundary elements, it only needs to be greater than its single neighbor. We are searching for an element that satisfies this specific property, not a particular value. By comparing an element at `mid` with its right neighbor at `mid + 1`, we can determine if the local "slope" is rising or falling.

Dry Running the Algorithm

The algorithm initializes `left` and `right` pointers to the array boundaries. In each step, it calculates a `mid` index. If `nums[mid]` is less than `nums[mid + 1]`, it indicates an uphill slope, meaning a peak must exist to the right of `mid`. Thus, the `left` pointer moves to `mid + 1`. If `nums[mid]` is greater than or equal to `nums[mid + 1]`, it indicates a downhill or flat slope, meaning a peak is at or to the left of `mid`. In this case, the `right` pointer moves to `mid`. The search continues until `left` and `right` pointers converge, at which point `left` (or `right`) will be the index of a peak element.

function findPeakElement(nums):
  left = 0
  right = nums.length - 1

  while left < right:
    mid = left + (right - left) / 2

    if nums[mid] < nums[mid + 1]:
      // Uphill slope, peak is to the right
      left = mid + 1
    else:
      // Downhill or flat slope, peak is at or to the left
      right = mid

  return left // left and right pointers have converged

Implementing the Code

The implementation involves a `while` loop that continues as long as `left` is less than `right`. Inside the loop, the `mid` index is calculated to prevent overflow. The core logic is the comparison: if `nums[mid]` is less than `nums[mid + 1]`, we know we are on an ascending slope, so we update `left = mid + 1`. Otherwise, we are on a descending or flat slope, and we update `right = mid`. The loop terminates when `left` and `right` become equal, and this converged index is returned as a peak.

The Mountain Analogy

Consider searching for a peak on a mountain range without a full map. If you take a step and find yourself going uphill, you know a peak must be further in that direction. If you take a step and find yourself going downhill, you know the peak must be behind you or at your current position. This local slope information allows you to eliminate half of your remaining search space with each comparison, much like binary search, efficiently guiding you to a peak element.

Key takeaways

• Binary search can find peak elements in unsorted arrays by leveraging local slope.
• A peak element is greater than its immediate neighbors.
• Comparing `nums[mid]` with `nums[mid + 1]` determines the local slope.
• If `nums[mid] < nums[mid + 1]`, the peak is to the right (`left = mid + 1`).
• If `nums[mid] >= nums[mid + 1]`, the peak is at or to the left (`right = mid`).