把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素，例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。

NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

1、利用二分法寻找数组中的最小元素

2、定义两个 指针left和right,指向数组的第一个元素和最后一个元素，定义一个中间指针mid

3、如果arr[left]小于arr[mid],那么把左边指针移动到mid处，mid从新计算 4.如果arr[left]大于arr[mid],那么把右边指针移动到mid处，mid从新计算，缩小范围

1. left=0 right=arr.length-1 
2. while arr[left]>=arr[right] 
3.   if right-left==1 
4.     mid=right 
5.     break 
6.   mid=left+(right-left)/2 
7.   if arr[left]<=arr[mid] 
8.     left=mid 
9.   else 
10.     right=mid 
11. return arr[mid] 
12.  
13. <?php 
14. $arr=array(3,4,5,6,1,2); 
15. function minNumberInRotateArray($rotateArray){ 
16.     $left=0;//左边指针 
17.     $right=count($rotateArray)-1;//右边指针 
18.     //判断条件，left大于right就一直进行 
19.     while($rotateArray[$left]>=$rotateArray[$right]){ 
20.         //left和right已经紧挨着了 
21.         if(($right-$left)==1){ 
22.             $mid=$right; 
23.             break; 
24.         }   
25.         //中间点 
26.         $mid=ceil($left+($right-$left)/2); 
27.         //left小于中间点 
28.         if($rotateArray[$left]<$rotateArray[$mid]){ 
29.             //left移动到中间点 
30.             $left=$mid; 
31.         }else{ 
32.             //right移动到中间点 
33.             $right=$mid; 
34.         }   
35.     }   
36.      
37.     return $rotateArray[$mid]; 
38. } 
39. $min=minNumberInRotateArray($arr); 
40. var_dump($min);//int(1)

Tags: php有序数组 php寻找最小值

分享到：