資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學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 迴圈重複地將搜尋範圍減半，直到找到目標值或範圍為空。它具有簡單的實現方式，並且適用於大多數場景。另一方面，遞迴方法使用遞迴函式執行二分查詢。它遵循與迭代方法相同的邏輯，但使用函式呼叫而不是迴圈。遞迴二分查詢提供了更簡潔的實現，但由於函式呼叫堆疊操作，可能會有稍微更高的開銷。總的來說，兩種方法都提供了有效且可靠的執行二分查詢操作的方式。
更新於：2023年7月28日
1K+ 次瀏覽
廣告