Find Peak Element

    Given an input array where , 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] = -∞.

    Note:

    Your solution should be in logarithmic complexity.

    Credits:

    Special thanks to @ts for adding
    this problem and creating all test cases.

    由时间复杂度的暗示可知应使用二分搜索。首先分析若使用传统的二分搜索，若A[mid] > A[mid - 1] && A[mid] < A[mid + 1]，则找到一个peak为A[mid]；若，则A[mid]左侧必定存在一个peak，可用反证法证明：若左侧不存在peak，则A[mid]左侧元素必满足A[0] > A[1] > ... > A[mid -1] > A[mid]，与已知A[0] < A[1]矛盾，证毕。同理可得若A[mid + 1] > A[mid]，则A[mid]右侧必定存在一个peak。如此迭代即可得解。
    由于题中假设端点外侧的值均为负无穷大，即, 那么问题来了，这样一来就不能确定峰值一定存在了，因为给定数组为单调序列的话就咩有峰值了，但是实际情况是——题中有负无穷的假设，也就是说在单调序列的情况下，峰值为数组首部或者尾部元素，谁大就是谁了。

    Python

    Java

    典型的二分法模板应用，需要注意的是需要考虑单调序列的特殊情况。当然也可使用紧凑一点的实现如改写循环条件为l < r，这样就不用考虑单调序列了，见实现2.

    复杂度分析

    二分法，时间复杂度 O(\log n).

    Java - compact implementation[^leetcode_discussion]

    C++ 的代码可参考 Java 或者 的实现。