[PHP]算法-旋转数组的最小值的PHP实现

<div class="cnblogs_code">

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,51.<span style="color: #000000">可以看成是二分查找法，查找最小的元素

2.{3,2} 可以看成{3,5} {1,2<span style="color: #000000">}，left和right两个指针分别指向第一个和最后一个

3.mid=left+(right-left)/2 如果arr[left] <= arr[mid]  那么 left指针移到mid处，left=<span style="color: #000000">mid

如果arr[left] > arr[mid]那中间元素必定是在右半区，right指针移到mid处  right=<span style="color: #000000">mid

4.终止条件是right-left=1 mid=<span style="color: #000000">right

5.<span style="color: #000000">

minNumberInRotateArray(arr)

<span style="color: #0000ff">while arr[left]><span style="color: #000000">arr[right]

<span style="color: #0000ff">if (right-left)==1<span style="color: #000000">

mid=<span style="color: #000000">right

<span style="color: #0000ff">break<span style="color: #000000">

mid=left+(right-left)/2

<span style="color: #0000ff">if arr[left]<=<span style="color: #000000">arr[mid]

left=<span style="color: #000000">mid

<span style="color: #0000ff">else<span style="color: #000000">

right=<span style="color: #000000">mid

<span style="color: #0000ff">return arr[mid]

<div class="cnblogs_Highlighter">
<pre class="brush:php;gutter:true;">function minNumberInRotateArray($arr)
{
$left=0;
$size=count($arr);
$right=$size-1;
$mid=$left+intval(($right-$left)/2);
while($arr[$left]>=$arr[$right]){
if(($right-$left)==1){
$mid=$right;
break;
}
$mid=$left+intval(($right-$left)/2);
if($arr[$left]<=$arr[$mid]){
$left=$mid;
}else{
$right=$mid;
}
}
return $arr[$mid];
}

$arr=array(3,2);
$m=minNumberInRotateArray($arr);
var_dump($m);

（编辑：安卓应用网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!