<?php 
/**
 * 题目：
 * 旋转数组最小的元素
 * 题目描述：
	把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
   思路：
    旋转将数组分为两个数组
    前面元素都大于后面元素
    二分法
 */
function minNumberInRotateArray($rotateArray)
{
    $left = 0;
    $right = count($rotateArray) - 1;
    $min = 0;
    while($rotateArray[$left] >= $rotateArray[$right]) {
    	// 分界点
    	if ($right - $left == 1) {
    		$min = $right;
    		break;
    	}
        // rotateArray[left] rotateArray[right] rotateArray[mid]三者相等
        // 无法确定中间元素是属于前面还是后面的递增子数组
        // 只能顺序查找
        
        $mid = $left + intval(($right - $left) / 2);
        if ($rotateArray[$left] == $rotateArray[$right] && $rotateArray[$left] == $rotateArray[$mid]) {
        	return MinOrder($rotateArray,$left,$right);
        }
        
      
    	if ($rotateArray[$mid] >= $rotateArray[$left]) {
    		$left = $mid;
    	} else {
    		$right = $mid;
    	}
    }
    return $rotateArray[$mid];
}

 // 顺序寻找最小值
function MinOrder($rotateArray,$left,$right)
{
	$min = $rotateArray[$left];
	for ($i = $left + 1;$left <= $right;$left++) {
		if ($min > $rotateArray[$left]) {
			$min = $rotateArray[$left];
		}
	}
	return $min;
}

$arr = [3,4,5,1,2];
$arr = [1,1,1,0,1];
$min = minNumberInRotateArray($arr);
echo $min;