> For the complete documentation index, see [llms.txt](https://zedive.gitbook.io/project-l/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://zedive.gitbook.io/project-l/part-2/divide_and_conquer/binary_search/find-troughpeak-element.md).

# Find Trough/Peak Element

## Find Peak Element ([LC.162](https://leetcode.com/problems/find-peak-element/))

> Given an input array where num\[i] ≠ num\[i+1], find a peak element and return its index.

The array may contain multiple peaks, in that case return the index to any one of the peaks is fine. You may imagine that num\[-1] = num\[n] = -∞.

## Example

```
Input: [1, 2, 3, 1]
Return: A[2] = 3, return 2
Input: [1, 2, 1, 3, 4, 5, 7, 6]
Return: A[1] = 2 or A[6] = 7, return 1 or 6
```

## Analysis

This is more fun to do. This is no longer a vanilla binary search. This is decrease and conquer. We need to exploit the sorted property and somehow pick half of the original problem to solve. We have 4 cases:\
1\. mid is peak, then A\[mid-1] < A\[mid] < A\[mid+1]\
2\. if the seq is increasing, then search right\
3\. if the seq is decreasing, then search left\
4\. else mid is a trough, either left or right is fine

## Code

```java
public int findPeakElement(int[] nums) {
    if (nums == null || nums.length == 0) {
        return -1;
    }
    return peakHelper(nums, 0, nums.length - 1);
}

private int peakHelper(int[] nums, int start, int end) {
    // base case 2 elements (make sure no array out of bound exception)
    if (start + 1 >= end) {
        if (nums[start] > nums[end]) {
            return start;
        } else {
            return end;
        }
    }
    // decrease
    int mid = start + (end - start) / 2;
    // conquer
    if (nums[mid - 1] < nums[mid] && nums[mid] > nums[mid + 1]) {
        // nums[mid] is a peak
        return mid;
    } else if (nums[mid - 1] < nums[mid] && nums[mid] < nums[mid + 1]) {
        // in an increasing seq, search right
        return peakHelper(nums, mid + 1, end);
    } else if (nums[mid - 1] > nums[mid] && nums[mid] > nums[mid + 1]) {
        // in a decreasing sq, search left
        return peakHelper(nums, start, mid - 1);
    } else {
        // a trough, either left or right
        return peakHelper(nums, start, mid - 1);
    }
}
```

The comparisons can be further simplified. But since we have a clear understanding and a working code, objectives accomplished.

## Maximum Number in Mountain Sequence

> Given a mountain sequence of n integers which increase firstly and then decrease, find the mountain top.

## Example

```
Given nums = [1, 2, 4, 8, 6, 3] return 8
Given nums = [10, 9, 8, 7], return 10
```

## Analysis

Same thing as above. Let's try while loop this time.

## Code

```java
public int mountainSequence(int[] nums) {
    if (nums == null || nums.length == 0)
        return -1;
    int start = 0, mid, end = nums.length - 1;
    // guarantee more than 2 elements
    while (start + 1 < end) {
        mid = (start + end) / 2;
        if (nums[mid - 1] < nums[mid] && nums[mid] > nums[mid + 1]) {
            // a peak
            return nums[mid];
        } else if (nums[mid - 1] < nums[mid] && nums[mid] < nums[mid + 1]) {
            // increasing seq, search right
            start = mid + 1;
        } else {
            // decreasing seq, or a trough, search left
            end = mid - 1;
        }
    }
    // base case
    if (nums[start] > nums[end]) {
        return nums[start];
    } else {
        return nums[end];
    }
}
```

## Find Peak Element II

Find peak in a 2D array.

## Reference

[Find Peak Element](https://segmentfault.com/a/1190000003488794) by segmentfault