题解 | #寻找峰值#

二分查找的本质

• 二分查找的本质是二段性，二分查找的过程本质是对可行区间的压缩，只要满足二段性的问题都可以用二分查找解决。
• 此题的二段性体现在峰值的左边单调增，右边单调减。

二分查找的分类

• 左闭右开型：while循环中，left和right之间没有等号，中间值选取为mid=(left+right)/2，中间值偏向左边，是左闭右开型，适合用于寻找上界。
• 左开右闭型：while循环中，left和right之间没有等号，中间值选取为mid=(left+right+1)/2，中间值偏向右边，是左开右闭型，适合用于寻找下界。

使用左闭右开型二分查找寻找峰值

• 根据首尾指针确定一个中间值，如果这个中间值大于右边相邻的值，说明这个中间值有可能是峰值，下次在[left, mid)中寻找峰值。
• 如果中间值小于右边相邻的值，此时处于上坡阶段，这个中间值不可能是峰值，下次在[mid+1, right)中寻找峰值。

参考

https://blog.csdn.net/whc18858/article/details/122379930?spm=1001.2014.3001.5501

https://blog.nowcoder.net/n/a9a4a9f3b09f46d38d2dd80e1a7f272d?f=comment

https://blog.nowcoder.net/n/eafbb55131ec4e7f83360ed84c7ad911?f=comment

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param nums int整型一维数组 
 * @return int整型
 */
function findPeakElement( nums ) {
    // write code here
    let left = 0;
    let right = nums.length-1;
    let middle;

    while (left < right) {
        middle = Math.floor((left+right)/2);

        if (nums[middle] < nums[middle+1]) {
            // 说明此时在上坡，峰值在右边区间
            left = middle+1;
        }
        else if (nums[middle] > nums[middle+1]){
            // 说明此时在下坡，middle可能是峰值
            right = middle;
        }
    }

    return left;
}
module.exports = {
    findPeakElement : findPeakElement
};