首頁 > 後端開發 > php教程 > 在PHP中進行二分查找

在PHP中進行二分查找

王林
發布: 2023-08-28 08:02:01
轉載
1429 人瀏覽過

在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中文網其他相關文章!

來源:tutorialspoint.com
本網站聲明
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn
最新問題
熱門教學
更多>
最新下載
更多>
網站特效
網站源碼
網站素材
前端模板