function binary_search($arr, $start, $end, $target) {
if ($start<= $end) {
$mid = intval(($start + $end) / 2);
if ($arr[$mid] == $target) {
return $mid;
} elseif ($arr[$mid] >$target) {
return binary_search($arr, $start, $mid - 1, $target);
} else {
return binary_search($arr, $mid + 1, $end, $target);
}
}
return -1;
}
$arr = array(1, 3, 5, 7, 9, 11, 13);
$target = 7;
$res = binary_search($arr, 0, count($arr) - 1, $target);
echo $res; // 3
以上代碼是一個基本的php實現二分查找法的例子,通過遞歸調用實現數據范圍的縮小和查找過程。 首先對于有序的數組,設定查找的起始位置$start和結束位置$end,然后計算出中間元素的下標$mid。如果中間元素等于目標元素,則直接返回中間元素的下標;如果中間元素大于目標元素,則在前半部分繼續查找;如果中間元素小于目標元素,則在后半部分繼續查找。 如果查找范圍沒有找到目標元素,則返回-1。
$arr = array(2, 4, 6, 8, 10);
$target = 5;
$res = binary_search($arr, 0, count($arr) - 1, $target);
echo $res; // -1
在上述代碼中,我們定義了一個含有五個元素的int數組$a,并將目標元素$target設為5,因為數組a中并沒有5這個元素,所以查找結果返回-1。
$arr = array(2, 4, 6, 8, 10);
$target = 4;
$res = binary_search($arr, 0, count($arr) - 1, $target);
echo $res; // 1
在上述代碼中,我們仍然定義了同樣的int數組$a,但是這次我們將目標元素設為4,由于數組a中存在4這個元素,所以查找結果返回1。
通過以上三個不同的例子,我們可以看到使用php實現二分查找法可以對于數組元素的查找實現高效的處理。 由于二分查找法需要有序數組作為基礎,所以在應用時需要保證輸入的數組已經排好序。其次,對于大數量級的數據,二分查找法的效率遠高于順序查找,因此在實際應用中也有較為廣泛的應用。
上一篇php 中文文件下載
下一篇php 中級面試題