在PHP中進行二分查找

什麼是二分查找？

二分搜尋是一種搜尋演算法，用於有效地尋找排序數組（或清單）中目標值的位置。它的工作原理是重複將搜尋範圍一分為二，並將中間元素與目標值進行比較。

二分查找演算法遵循以下步驟：

• 從整個排序數組開始。

• 將左指標設定為陣列的第一個元素，將右指標設定為最後一個元素。

• 計算中間索引作為左右指標的平均值（整數除法）。

• 將中間索引處的值與目標值進行比較。

• 如果中間值等於目標值，則搜尋成功，演算法會傳回索引。

• 如果目標值大於中間值，則透過將左指標更新為 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中文網其他相關文章！