<?php


/*
- [BM19 尋找峰值](http://fangfengwang8.cn/share/jump/4163484761690942105670)
- 時間復(fù)雜度  
*/


/**
 * 代碼中的類名、方法名、參數(shù)名已經(jīng)指定，請勿修改，直接返回方法規(guī)定的值即可
 *
 * 
 * @param nums int整型一維數(shù)組 
 * @return int整型
 */
function findPeakElement( $nums )
{
    // write code here
    // 峰值元素是指其值嚴(yán)格大于左右相鄰值的元素。嚴(yán)格大于即不能有等于
    // 你可以假設(shè) nums[-1] = nums[n] = -∞
    $size = count($nums);
    $left = 0;
    $right= $size - 1;

    while($left < $right) {
        $mid = $left + (($right - $left) >> 1);
        if($nums[$mid] > $nums[$mid + 1]) {
            // 下降區(qū)間，不一定有峰值
            // 左邊高，說不定左邊就是峰值，可能 mid 就是
            $right = $mid;
        } else {
            // 上升區(qū)間，可能有峰值
            // 右邊高，說明在mid右邊有峰值，
                // 如果是nums[mid] < nums[mid + 1]，那么mid肯定不是
                // 如果是nums[mid] = nums[mid + 1]，那么mid也不需要考慮
            $left = $mid + 1;
        }
    }

    // 左右指針
    return $left;

}



$nums = [2,4,1,2,7,8,4];
// left=0 right=6 mid=3 
    // nums[3] < nums[4] 上升
    // left = 3 + 1 = 4
// left=4 right=6 mid=5
    // nums[5] > num[6] 下降
    // right = 5
// left=4 right=5 mid=4
    // nums[4] < nums[5] 上升
    // left = 4 + 1 = 5
// left=5 right=5 
    // 返回
var_dump(findPeakElement($nums));