题解 | #寻找峰值#

<?php


/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param nums int整型一维数组 
 * @return int整型
 */
function findPeakElement( $nums )
{
    return binary_find_peak($nums, 0, count($nums)-1);
}

function binary_find_peak($nums, $lower, $higher){
    if($lower >= $higher){
        return $lower;
    }
    $mid = intval(($lower+$higher)/2);
    if($nums[$mid] > $nums[$mid+1]){
        return binary_find_peak($nums, $lower, $mid);
    }else{
        return binary_find_peak($nums, $mid+1, $higher);
    }
    return $mid;
}

由于nums[i] != nums[i+1]，可知一定存在一个峰值。

如果nums[mid] > nums[mid+1]，那么nums[0]~nums[mid]中一定存在一个峰值，可以舍弃nums[mid+1]~nums[len-1]这一段

如果nums[mid] < nums[mid+1]，那么nums[mid+1]~nums[len-1]中一定存在一个峰值，可以舍弃nums[0]~nums[mid]这一段

递归停止条件：lower >= higher，返回lower（因为本次递归中lower==higher的时候就会停止）

复杂度：O（logn）