在php中我們可以通過array_search()函數來查找一個數組內的元素值的鍵名.
同樣,我們可以通過使用二分法來查找數組內的元素的鍵名.
那什麼是二分法呢?
我來解釋下:
如果數據是按升序排序的,我們從數據的中間位置開始查找,若給定的值恰好等於當前位置的值,查找成功,若給定的值小於當前位置的值,那我們就從以當前值為准查找其前半部分的值,反之,若給定的值大於當前值,那麼就從以當前值為准查找其後半部分的值.
也就是說,利用二分法查找的數據,必須是排好序的.
下面我們嘗試查找數組array(1,2,3,4,5,6,7,8,9,10)中的某一個值的位置:
<?php
function Search($a,$val){
$low = 0;
$high= count($a) - 1;
while($low <= $high){
$mid = intval(($low+$high)/2);
if($a[$mid] == $val)
return $mid;
if($a[$mid] > $val){
$high = $mid - 1;
}else{
$low = $mid + 1;
}
}
return -1;
}
?>
以上函數,第一個參數為傳入的數組,第二個參數為該數組需要查詢的值.
我們給數組的鍵設置一個最小值$low為0,設置一個最大值為$high為數組長度減一,那麼中間值我們就可以設置為intval(($low+$height)/2),
也就是說,當數組元素長度為奇數時,數組的中間值正好在正中間,
例如數組長度為5,那中間值正好為2,也就是(0+4)/2,
0,1,2,3,4
那當我們的數組長度為偶數時,利用上述公式是無法除盡的,所以我們要取整,無論是進一法取整還是捨去法取整都是可以的
例如數組長度為6,那中間值為(0+5)/2,值為2.5,那數組中鍵為2.5的是不存在的,所以我們就需要取整為2
0,1,2,3,4,5
如果使用上述取整函數intval或者是floor函數獲得的鍵為2,如果使用ceil取整,這裡得到的鍵即為3
那麼,我們拿上面的數組來說:
數組的長度為10,那麼中間值即為intval((0+(10-1))/2),為4,索引為4的也就是數組中的第五個元素"5"
1,2,3,4,5,6,7,8,9,10
好,我們下面開始判斷,
1.如果需要查詢的值恰好為"5",查找成功,直接返回該值的索引即可.
也就是
if($a[$mid] == $val)
return $mid;
2.如果要查詢的值小於"5",我們需要把$high的值設為中間值減一,即為4-1,並返回繼續查詢中間值的前半部分(紅色部分)
1,2,3,4,5,6,7,8,9,10
即為:
if($a[$mid] > $val){
$high = $mid - 1;
}
3.如果要查詢的值大於"5",我們就需要把$low的值設為中間值加一,即為4+1,並返回繼續查詢中間值的後半部分(紅色部分)
1,2,3,4,5,6,7,8,9,10
即為:
else{
$low = $mid + 1;
}
設置完之後,返回繼續查詢,如果滿足條件$low<=$high,就反復查詢,直到此條件不成立,也就是被查詢的范圍小於一個數組元素時,說要查詢的值在數組中不存在,返回-1
while($low <= $high){
.......
}
return -1;
此函數的缺點在於:
如果數組中有重復的值,只能查到其中的一個值的鍵,有興趣的童鞋,可以對以上函數進行完善,跟帖回復.
摘自 zdrjlamp
