LeetCode 852 - Peak Index in a Mountain Array

https://leetcode.com/problems/peak-index-in-a-mountain-array/

Let's call an array A a mountain if the following properties hold:

• A.length >= 3
• There exists some 0 < i < A.length - 1 such that A[0] < A[1] < ... A[i-1] < A[i] > A[i+1] > ... > A[A.length - 1]

Given an array that is definitely a mountain, return any i such that A[0] < A[1] < ... A[i-1] < A[i] > A[i+1] > ... > A[A.length - 1].

X. https://medium.com/datadriveninvestor/golden-section-search-method-peak-index-in-a-mountain-array-leetcode-852-a00f53ed4076

# 2) Binary Search, define left and right pointers and compute mid for each iteration. When A[mid]<A[mid+1] , indicating the numbers are still increasing, so the peak shall occur on the right side of mid , hence we update left pointer; Otherwise it indicates peak shall occur on the left side of mid , we update the right pointer. Eventually, two pointers meet and the peak index is located. Olog(N) time complexity, much faster if we have a large input.

https://nifannn.github.io/2018/06/29/Algorithm-Notes-Leetcode-852-Peak-Index-in-a-Mountain-Array/

We can solve this problem with binary search. First, we find the middle value of the array A[mid] (mid = (A.length - 1) // 2). If A[mid-1] < A[mid] > A[mid+1], then A[mid] is the peak, just return mid. If A[mid-1] < A[mid] < A[mid+1], then the peak is in A[mid+1:]. If A[mid-1] > A[mid] > A[mid+1], then the peak is in A[:mid]. As a result, we reduce the range we search for the peak. Similarly, we can repeat finding the middle value, reducing the search range and finding new middle value until we find the peak.

https://nifannn.github.io/2018/06/29/算法笔记-Leetcode-852-Peak-Index-in-a-Mountain-Array/

可以用二分法来解决。先找到整个数组的中间值A[mid] (mid = (A.length - 1) // 2)，如果A[mid-1] < A[mid] > A[mid+1]，A[mid]就是山峰，直接返回mid。如果A[mid-1] < A[mid] < A[mid+1]，则峰值落于A[mid+1:]。如果A[mid-1] > A[mid] > A[mid+1]，则峰值位于A[:mid]。然后就可以缩小范围，继续寻找。总之，可以先找中间值，然后缩小范围，再找中间值，缩小范围，不停反复，直到找到我们要的峰值，输出其索引。

https://blog.csdn.net/fuxuemingzhu/article/details/80721162

这个比普通二叉搜索的改进地方就是不再判断left, mid, right三者之间的关系。而是对于中间的mid，去判断mid和其相邻的两个元素的关系。根据是否符合山峰的上坡和下坡，去移动指针。

    def peakIndexInMountainArray(self, A):
        """
        :type A: List[int]
        :rtype: int
        """
        left, right = 0, len(A) - 1
        while left < right:
            mid = (left + right) / 2
            if A[mid - 1] < A[mid] and A[mid] < A[mid + 1]:
                left = mid
            elif A[mid - 1] > A[mid] and A[mid] > A[mid + 1]:
                right = mid
            else:
                break
        return mid

二刷的时候，写了一个打败100%的写法，也就是我们使用了更少的判断。

    def peakIndexInMountainArray(self, A):
        """
        :type A: List[int]
        :rtype: int
        """
        N = len(A)
        left, right = 0, N
        while left < right:
            mid = left + (right - left) // 2
            if A[mid - 1] < A[mid] and A[mid] > A[mid + 1]:
                return mid
            if A[mid] < A[mid + 1]:
                left = mid + 1
            else:
                right = mid
        return -1

查找最大值位置

这个做法是在题目保证了给出的数组是满足条件的，那么只要找出最大值的位置那么一定就满足了条件。

    def peakIndexInMountainArray(self, A):
        return A.index(max(A))

寻找第一个下降的位置

题目给出的是满足条件的数组，所以找出第一个下降的位置就是题目所求啊。

    def peakIndexInMountainArray(self, A):
        """
        :type A: List[int]
        :rtype: int
        """
        for i in range(len(A) - 1):
            if A[i + 1] < A[i]:
                return i
        return -1

https://leetcode.com/problems/peak-index-in-a-mountain-array/discuss/139848/C%2B%2BJavaPython-Better-than-Binary-Search

The comparison A[i] < A[i+1] in a mountain array looks like [True, True, True, ..., True, False, False, ..., False]: 1 or more boolean Trues, followed by 1 or more boolean False. For example, in the mountain array [1, 2, 3, 4, 1], the comparisons A[i] < A[i+1] would be True, True, True, False.

We can binary search over this array of comparisons, to find the largest index i such that A[i] < A[i+1].

    public int peakIndexInMountainArray(int[] A) {
        int l = 0, r = A.length - 1, mid;
        while (l < r) {
            mid = (l + r) / 2;
            if (A[mid] < A[mid + 1]) l = mid;
            else if (A[mid - 1] > A[mid]) r = mid;
            else return mid;
        }
        return 0;
    }

Follow-up:
Can you do faster than binary search?

Approach 4, Golden-section search

It's gurentee only one peak, we can apply golden-section search.

    def peakIndexInMountainArray(self, A):
        def gold1(l, r):
            return l + int(round((r - l) * 0.382))

        def gold2(l, r):
            return l + int(round((r - l) * 0.618))
        l, r = 0, len(A) - 1
        x1, x2 = gold1(l, r), gold2(l, r)
        while x1 < x2:
            if A[x1] < A[x2]:
                l = x1
                x1 = x2
                x2 = gold1(x1, r)
            else:
                r = x2
                x2 = x1
                x1 = gold2(l, x2)
        return x1

Method 1: O(n)

    public int peakIndexInMountainArray(int[] A) {
        for (int i = 1; i < A.length; ++i) {
            if A[i] > A[i + 1]) { return i; }
        }
        return -1; // no peak.
    }

Method 2: O(log(n))

    public int peakIndexInMountainArray(int[] A) {
        int lo = 0;
        int hi = A.length - 1;
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if (A[mid] < A[mid + 1]) { lo = mid + 1; } // peak index is after mid.
            else{ hi = mid; } // peak index <= mid.
        }
        return lo; // found peak index.
    }

    public int peakIndexInMountainArray(int[] A) {
        for (int i = 1; i + 1 < A.length; ++i) if (A[i] > A[i + 1]) return i;
        // for (int i = A.length - 1; i > 0; --i) if (A[i] > A[i - 1]) return i;
        return 0;
    }

https://en.wikipedia.org/wiki/Golden-section_search

0.618法，又叫黄金分割法，是优选法的一种。它在试验时，把试点安排在黄金分割点上来寻找最佳点。而生产生活中，我们常常取其近似值0.618，因此得名。0.618法是最常用的单因素单峰目标函数优选法之一