写一个函数peak寻找一个数组的峰值位置。 比如数组: 1,3,5,7,4,2有峰值7；已排序数组1,2,3,4,5,6，有峰值6。有的数组有多个峰值，这里只需要返回任何一个。比如数组[1,2,3,2,7,6]有两个峰值3和7。

    如果一个元素左右元素都相同，那么这个元素就是峰值，比如数组1,1,1,1，每个元素都是峰值。

    例如

    1. peak([1,2,3,4,5,6])  // 5(6所在的位置）
    2. peak([1,3,5,7,4,2]) // 3（7所在的位置）
    3. peak([1,2,3,2,7,6]) // 2(3所在的位置)
    4. peak([1,1,1,1,1,1]) // 任何一个都是峰值

    如果有多个峰值，只要随便返回一个就可以，不需要考虑顺序。

    答案:

    参考二分查找，如果一次猜测不是峰值，那么分成两种情况：

    1. 左边数字大于猜测，那么左边一定存在峰值

    2. 右边数字大于猜测，那么右边一定存在峰值

    1. function is_peak(A, g) {
    2.   return ( g === 0 || A[g] >= A[g-1] )
    3.     && (g === A.length - 1 || A[g] >= A[g+1])
    4. }
    5. function peak(A) {
    6.   let l = 0,
    7.       r = A.length - 1,
    8.       guess
    10.   while(l <= r) {
    11.     const guess = Math.floor( (l+r) / 2)
    12.     if(is_peak(A, guess)) {
    13.       return guess
    14.     }
    16.     if(A[guess] < A[guess - 1]) {
    17.       r = guess - 1
    18.     }
    19.     else if(A[guess] < A[guess + 1]) {
    20.       l = guess + 1
    21.     }
    22.   }
    23. }
    25. //尾递归版
    26. function peak(A, l = 0, r = A.length -1) {
    27.   if(l <= r) {
    28.     const guess = Math.floor((l + r) / 2)
    29.     if(is_peak(A, guess)) {
    30.       return guess
    31.     }
    32.     if ( A[guess] < A[guess - 1]  ){
    33.       return peak(A, l, guess - 1)
    34.     }
    35.     else if ( A[guess] < A[guess + 1]) {
    36.       return peak(A, guess + 1, r)
    37.     }
    38.   }
    39. }

    以上复杂度O(lgn)