<?php
/**
 * @desc: 寻找最小值
 * @param null $arr
 * @return bool|int
 */
function findMin($arr=null){
    if(empty($arr)){
        return false;
    }
    $len=count($arr);
    $left=0;
    $right = $len - 1;
    while ($left < $right) {
        $mid = intval(($left + $right) / 2);
        if ($arr[$mid] > $arr[$left]) {//左半部分有序
            $left = $mid + 1;
        } else {
            $right = $mid - 1;
        }
    }
    return $mid;
}

/**
 * @desc: 查找旋转有序数组中的k
 * @param null $arr
 * @param null $k
 * @return bool|int
 */
function find($arr = null, $k = null)
{
    if(empty($arr)){
        return false;
    }
    $len=count($arr);
    $left=0;
    $right = $len - 1;
    while ($left= $arr[$left]) {//左半部分有序
            if ($k = $arr[$left]) {//k在左半部分中
                $right = $mid - 1;
            } else {
                $left = $mid + 1;
            }
        } else {//右半部有序
            if ($k  $arr[$mid]) {//k在右半部分钟
                $left = $mid + 1;
            } else {
                $right = $mid - 1;
            }
        }
    }
    if($arr[$mid]==$k){
        return $mid;
    }else{
        return -1;
    }
}

//$arr = [4, 5, 6, 7, 0, 1, 2];
$arr = [6, 7, 8, 0, 1, 2, 3, 4, 5];
var_dump(findMin($arr));
var_dump(find($arr,7));

赞0 2686次