php實(shí)現(xiàn)有序數(shù)組旋轉(zhuǎn)后尋找最小值方法
把一個(gè)數(shù)組最開(kāi)始的若干個(gè)元素搬到數(shù)組的末尾，我們稱之為數(shù)組的旋轉(zhuǎn)。 輸入一個(gè)非減排序的數(shù)組的一個(gè)旋轉(zhuǎn)，輸出旋轉(zhuǎn)數(shù)組的最小元素。 例如數(shù)組{3,4,5,1,2}為{1,2,3,4,5}的一個(gè)旋轉(zhuǎn)，該數(shù)組的最小值為1。
NOTE：給出的所有元素都大于0，若數(shù)組大小為0，請(qǐng)返回0。
1、利用二分法尋找數(shù)組中的最小元素
2、定義兩個(gè) 指針left和right,指向數(shù)組的第一個(gè)元素和最后一個(gè)元素，定義一個(gè)中間指針mid
3、如果arr[left]小于arr[mid],那么把左邊指針移動(dòng)到mid處，mid從新計(jì)算 4.如果arr[left]大于arr[mid],那么把右邊指針移動(dòng)到mid處，mid從新計(jì)算，縮小范圍
left=0 right=arr.length-1
while arr[left]>=arr[right]
if right-left==1
mid=right
break
mid=left+(right-left)/2
if arr[left]<=arr[mid]
left=mid
else
right=mid
return arr[mid]
<?php
$arr=array(3,4,5,6,1,2);
function minNumberInRotateArray($rotateArray){
$left=0;//左邊指針
$right=count($rotateArray)-1;//右邊指針
//判斷條件，left大于right就一直進(jìn)行
while($rotateArray[$left]>=$rotateArray[$right]){
//left和right已經(jīng)緊挨著了
if(($right-$left)==1){
$mid=$right;
break;
}
//中間點(diǎn)
$mid=ceil($left+($right-$left)/2);
//left小于中間點(diǎn)
if($rotateArray[$left]<$rotateArray[$mid]){
//left移動(dòng)到中間點(diǎn)
$left=$mid;
}else{
//right移動(dòng)到中間點(diǎn)
$right=$mid;
}
}
return $rotateArray[$mid];
}
$min=minNumberInRotateArray($arr);
var_dump($min);//int(1)
以上就是php如何實(shí)現(xiàn)有序數(shù)組旋轉(zhuǎn)后尋找最小值（代碼）的詳細(xì)內(nèi)容，感謝大家對(duì)腳本之家的支持。
相關(guān)文章
這篇文章主要介紹了PHP屏蔽過(guò)濾指定關(guān)鍵字的方法,包含了字符串的過(guò)濾處理與數(shù)組的遍歷等技巧,非常具有實(shí)用價(jià)值,需要的朋友可以參考下2014-11-11
這篇文章主要介紹了PHP清除數(shù)組中所有字符串兩端空格的方法,主要涉及對(duì)PHP數(shù)組的操作以及字符串操作,非常具有實(shí)用價(jià)值,需要的朋友可以參考下2014-10-10
自己寫(xiě)了一個(gè)php檢測(cè)文件編碼的函數(shù)
關(guān)于文件編碼的檢測(cè)，百度一下一大把都是，但是確實(shí)沒(méi)有能用的，下面是自己寫(xiě)了一個(gè)檢測(cè)函數(shù)，希望對(duì)大家有所幫助2014-04-04
php相對(duì)當(dāng)前文件include其它文件的方法
這篇文章主要介紹了php相對(duì)當(dāng)前文件include其它文件的方法,實(shí)例分析了php中include引入文件的使用技巧,非常具有實(shí)用價(jià)值,需要的朋友可以參考下2015-03-03
瀏覽器關(guān)閉后，能繼續(xù)執(zhí)行的php函數(shù)(ignore_user_abort)
希望關(guān)閉瀏覽器后，程序能繼續(xù)在后臺(tái)跑，這種情況下需要用到ignore_user_abort()函數(shù)2012-08-08
這篇文章主要介紹了PHP獲取客戶端及服務(wù)器端IP的封裝類,簡(jiǎn)單分析了php使用服務(wù)器預(yù)定義變量的基本用法并進(jìn)行了簡(jiǎn)單封裝,需要的朋友可以參考下2016-07-07
最近需要做到交叉表，而公司的需求比較復(fù)雜，一般的交叉表工具都不適合用2010-08-08
PHP采集靜態(tài)頁(yè)面并把頁(yè)面css,img,js保存的方法
這篇文章主要介紹了PHP采集靜態(tài)頁(yè)面并把頁(yè)面css,img,js保存的方法,可以實(shí)現(xiàn)簡(jiǎn)單的網(wǎng)頁(yè)抓取功能,具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2014-12-12
exec()是用于執(zhí)行shell命令的函數(shù)，下面說(shuō)的就是如何使用他用于shell注入的方法講解2013-11-11
PHP使用Http Post請(qǐng)求發(fā)送Json對(duì)象數(shù)據(jù)代碼解析
這篇文章主要介紹了PHP使用Http Post請(qǐng)求發(fā)送Json對(duì)象數(shù)據(jù)代碼解析,文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-07-07