什麼是二分查找？
二分搜尋是一種搜尋演算法，用於有效地尋找排序數組（或清單）中目標值的位置。它的工作原理是重複將搜尋範圍一分為二，並將中間元素與目標值進行比較。
二分查找演算法遵循以下步驟：
從整個排序數組開始。
將左指標設定為陣列的第一個元素，將右指標設定為最後一個元素。
計算中間索引作為左右指標的平均值（整數除法）。
將中間索引處的值與目標值進行比較。
如果中間值等於目標值，則搜尋成功，演算法會傳回索引。
如果目標值大於中間值，則透過將左指標更新為 mid 1 來消除搜尋範圍的左半部。
如果目標值小於中間值，則透過將右指標更新為 mid - 1 來消除搜尋範圍的右半部。
重複步驟3到7，直到找到目標值或搜尋範圍為空（左指標大於右指標）。
如果搜尋範圍為空且未找到目標值，則演算法會得出結論：目標值不存在於陣列中並傳回 -1 或適當的指示。
二分查找是一種非常有效率的演算法，時間複雜度為 O(log n)，其中 n 是數組中元素的數量。它對於大型排序數組特別有效，因為它透過在每一步將搜尋範圍一分為二來快速縮小搜尋範圍，即使有大量元素也可以快速搜尋。
二分查找的 PHP 程式
方法 1 - 使用迭代
範例
<?php
function binarySearch($arr, $target) {
$left = 0;
$right = count($arr) - 1;
while ($left <= $right) {
$mid = floor(($left + $right) / 2);
// Check if the target value is found at the middle index
if ($arr[$mid] === $target) {
return $mid;
}
// If the target is greater, ignore the left half
if ($arr[$mid] < $target) {
$left = $mid + 1;
}
// If the target is smaller, ignore the right half
else {
$right = $mid - 1;
}
}
// Target value not found in the array
return -1;
}
// Example usage 1
$sortedArray = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91];
$targetValue = 91;
$resultIndex = binarySearch($sortedArray, $targetValue);
if ($resultIndex === -1) {
echo "Target value not found in the array.<br>";
} else {
echo "Target value found at index $resultIndex.<br>";
}
// Example usage 2
$targetValue = 42;
$resultIndex = binarySearch($sortedArray, $targetValue);
if ($resultIndex === -1) {
echo "Target value not found in the array.";
} else {
echo "Target value found at index $resultIndex.";
}
?>
登入後複製
輸出
Target value found at index 9.
Target value not found in the array.
登入後複製
方法 2 - 使用遞迴
範例
<?php
function binarySearchRecursive($arr, $target, $left, $right) {
if ($left > $right) {
// Target value not found in the array
return -1;
}
$mid = floor(($left + $right) / 2);
// Check if the target value is found at the middle index
if ($arr[$mid] === $target) {
return $mid;
}
// If the target is greater, search the right half
if ($arr[$mid] < $target) {
return binarySearchRecursive($arr, $target, $mid + 1, $right);
}
// If the target is smaller, search the left half
return binarySearchRecursive($arr, $target, $left, $mid - 1);
}
// Wrapper function for the recursive binary search
function binarySearch($arr, $target) {
$left = 0;
$right = count($arr) - 1;
return binarySearchRecursive($arr, $target, $left, $right);
}
// Example usage
$sortedArray = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91];
$targetValue = 16;
$resultIndex = binarySearch($sortedArray, $targetValue);
if ($resultIndex === -1) {
echo "Target value not found in the array.";
} else {
echo "Target value found at index $resultIndex.";
}
?>
登入後複製
輸出
Target value found at index 4.
登入後複製
結論
總之，二分搜尋是一種強大的演算法，可以在排序數組中有效地找到目標值。它提供了兩種常見的實作：迭代和遞歸。迭代方法使用 while 迴圈重複將搜尋範圍一分為二，直到找到目標值或範圍變空。它具有簡單的實作方式，非常適合大多數場景。另一方面，遞歸方法採用遞歸函數來執行二分搜尋。它遵循與迭代方法相同的邏輯，但使用函數呼叫而不是循環。遞歸二分搜尋提供了更簡潔的實現，但由於函數呼叫堆疊操作可能具有稍高的開銷。總的來說，這兩種方法都提供了執行二分搜尋操作的高效可靠的方法。
以上是在PHP中進行二分查找的詳細內容。更多資訊請關注PHP中文網其他相關文章！
